• 动态规划: dp+递推——确定动态矩阵dp含义,确定每个状态下面临的选择和对结果值影响，选择符合题意的作为结果存储在dp中

    1、动态规划：每一个状态一定是由之前的状态推导出来的，通过总结归纳发现递推关系

    2、解决动态规划问题的步骤：

    • 确定dp数组（dp table）以及下标的含义：   
      • 每个单元内 题目所求的值，一维、二维
    • 确定递推公式：     
      • 当前元素面临的情况（是否相等、是否可选），每种情况下的可能取值，其中选择符合题意的
    • dp数组如何初始化：
      • 根据初始状态下dp矩阵的含义设置，且不能影响后续的计算
    • 确定遍历顺序（根据递推公式，右侧表达式中值需优先计算）：
      • 根据递推公式中索引的变化顺序（小到大，大到小），同步
    • 举例推导dp数组，判断思路是否正确。

    目录

    3. 步骤示例：

    4、路径问题：所有可达到当前格点一步距离的路径数之和

    5、拆分问题: 难点—寻找递推关系，有哪些拆分情况？

    6、背包问题：解决方法

    背包 例题：

    6.1 成对/分成两个子集：求和/2，使得各子集趋近目标值（背包总含量），进行动态规划

    6.2 组合问题: 求组合个数：动态规划，求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]]； 求所有组合列表：回溯算法

    6.3 二维的01背包：即需要满足两个条件

    6.4 完全背包：物品可多次添加，嵌套顺序均可，小到大（遍历顺序不同，01背包：先物品，在背包大到小）

    6.5 求装满背包有几种方案：

    7、不同的数据结构类型，如何进行动态规划

    8、股票获取最大收益：写出所有状态下   的所有情况下的收益取最大值，用数组存储

    9、子序列问题：单一维度

    10. 子序列问题：公共序列（个数），或变为相等字符串（操作数），二维

    11、回文字符串的判断、统计

    3. 步骤示例：

    1. 示例：509. 斐波那契数
    2. class Solution {
    3.     public int fib(int n) {
    4.         if(n <= 1) return n;//考虑特殊情况
    5.         int[] F = new int[n+1];//确定dp数组
    6.         F[0] = 0;//初始化dp
    7.         F[1] = 1;
    8.         for(int i = 2; i <= n; i++){//确定遍历顺序
    9.             F[i] = F[i-1] + F[i-2];//确定递推表达式
    10.         }
    11.         return F[n];
    12.     }
    13. }
    14.  
    15. 70. 爬楼梯 到n 阶有多少种方法
    16. class Solution {
    17.     public int climbStairs(int n) {
    18.         if( n <= 2) return n;
    19.         int[] dp = new int[n+1];//n阶楼梯,存放n+1个数据，到每层个有多少种方法
    20.         //每次你可以爬 1 或 2 个台阶
    21.         dp[1] = 1;//只能一步
    22.         dp[2] = 2;//两个一步，或者，一个两步
    23.         //当前方法数 = dp[n-1] + dp[n-2] 一步到位，两步到
    24.         for(int i = 3; i<=n; i++){
    25.             dp[i] = dp[i-1] +dp[i-2];
    26.         }
    27.         return dp[n];
    28.     }
    29. }
    30.  
    31. class Solution {
    32.     //每次你可以爬 1 或 2 个台阶, 进阶为每次可爬1-m个台阶
    33.     public int climbStairs(int n) {
    34.         int[] dp = new int[n+1];
    35.         int m = 2;//设置可走步数
    36.         if(n == 1 || n == 2) return n;
    37.         dp[1] = 1;
    38.         dp[2] = 2;
    39.         for(int i = 3; i <= n; i++){
    40.             for(int j = 1; j <= m && i >= j; j++){
    41.                 dp[i] += dp[i-j];
    42.             }
    43.         }
    44.         return dp[n];
    45.     }
    46.  
    47.  
    48.  
    49. //746.达到楼梯顶部的最低花费
    50. class Solution {
    51.     // cost[i] 是从楼梯第 i 个台阶向上爬需要支付的费用,在尾处加一个0表示楼顶,
    52.     public int minCostClimbingStairs(int[] cost) {
    53.         if(cost == null || cost.length <= 1) return 0;
    54.         int[] dp = new int[cost.length+1];
    55.         //可选择向上爬一个或者两个台阶
    56.         dp[0] = cost[0];
    57.         dp[1] = cost[1];
    58.         for(int i = 2; i < cost.length+1; i++){
    59.             if(i == cost.length){
    60.                 dp[i] = Math.min(dp[i-1],dp[i-2]) + 0;
    61.             }else{
    62.                 dp[i] = Math.min(dp[i-1],dp[i-2]) + cost[i];//之前的最小消耗+当前需消耗值
    63.             }
    64.         }
    65.         return dp[cost.length];
    66.     }
    67. }

    4、路径问题：所有可达到当前格点一步距离的路径数之和

    62. 不同路径：每次只能向下或者向右移动一步。机器人试图达到网格的右下角

    63. 不同路径 II：考虑网格中有障碍物。从左上角到右下角将会有多少条不同的路

    三种方法：

    1. 递归，将路径比作N叉树进行 深度遍历，时间复杂度高，超出时间限制O（2^(N+M-1)-1)
    2. 数论（组合。排列），转化成数学问题，求解公式，注意数值精度和数值范围，防止溢出
    3. 动态规划，根据各节点之间的关系，逐步推到。
    1. // 动态规划
    2. class Solution {
    3. // 1.确定dp数组（dp table）以及下标的含义：dp[m][n]到达当前网格的路径数，下标：坐标
    4. // 2.确定递推公式：每次只能向下或者向右移动一步 dp[i][j] = dp[i-1][j] + dp[i][j-1] 
    5. // 3.dp数组如何初始化:不能后退 dp[0][j] =1,dp[i][0]=1,到达机器人所在行列只有一种路径，直走
    6. // 4.确定遍历顺序 ： 需一直i-1和j-1, 由上至下层次遍历
    7. // 5.举例推导dp数组，判断思路是否正确。
    8.     public int uniquePaths(int m, int n) {
    9.         int[][] dp = new int[m][n];
    10.         for(int i = 0; i < m; i++) dp[i][0] = 1;
    11.         for(int j = 0; j < n; j++) dp[0][j] = 1;
    12.         for(int i = 1; i < m; i++) {
    13.             for(int j = 1; j < n; j++){
    14.                 dp[i][j] = dp[i-1][j] + dp[i][j-1];
    15.             }
    16.         }
    17.         return dp[m-1][n-1];
    18.     }
    19. }
    20.  
    21. //考虑网格中有障碍物,求路径数
    22. class Solution {
    23.     //网格中的障碍物和空位置分别用 1 和 0, 有障碍物则可到达该位置的路径为0
    24.     //机器人每次只能向下或者向右移动一步,
    25.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
    26.         int m = obstacleGrid.length, n = obstacleGrid[0].length;
    27.         int[][] dp = new int[m][n];
    28.         if(obstacleGrid[m-1][n-1] == 1) return 0;
    29.         //若第一行、列有障碍物，则行列中障碍物之后的格点均无法到达
    30.         for(int i = 0; i< m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
    31.         for(int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
    32.         for(int i = 1; i< m; i++){
    33.             for(int j = 1; j< n; j++){
    34.                 if(obstacleGrid[i][j] == 1){
    35.                     dp[i][j] = 0;
    36.                 }else{
    37.                     dp[i][j] = dp[i-1][j] + dp[i][j-1];
    38.                 }
    39.             }
    40.         }
    41.         return dp[m-1][n-1];
    42.     }
    43. }
    44.  
    45. //数论方法  组合问题，到达终点的步数为：n-1+m-1，其中m-1步是向下走的，可形成的组合数，即路径数量
    46. class Solution {
    47.     public int uniquePaths(int m, int n) {
    48.         // int res = 1;
    49.         // double numerator = n+m-2 ,denominator = m-1;//分子：A(n+m-2)(m-1),分母：A(m-1)(m-1)
    50.         // for(int i = 0; i < m-1; i++){
    51.         //     res *= numerator/denominator;//会出现小数,损失精度了
    52.         //     numerator--;
    53.         //     denominator--;
    54.         // }
    55.         double numerator = 1 ,denominator = m-1;//分子：A(n+m-2)(m-1),分母：A(m-1)(m-1)
    56.         for(int i = 0; i < m-1; i++){
    57.              numerator *= (n+m-2-i);
    58.              while(denominator > 0 && numerator % denominator == 0){//表示当前分子可整除分母，避免精度损失和栈溢出
    59.                 numerator = numerator/denominator;
    60.                 denominator--;
    61.              }
    62.         }
    63.         return (int)numerator;
    64.     }
    65. }
    66.  
    67.  
    68. // //递归，深度优先遍历,会超出时间限制
    69. // class Solution {
    70. // // 每次只能向下或者向右移动一步 , 即每个节点只有两个方向，将路径比作二叉树，寻找可到达终点即n+m-2层的叶子结点的路径个数
    71. //     public int uniquePaths(int m, int n) {
    72. //         return dfs(m-1,n-1,m,n);
    73. //     }
    74. //     public int dfs(int i, int j,int m, int n){
    75. //         if(i == 0 || j == 0) return 1;//到达（i，j)节点的路径只有一个
    76. //         return dfs(i-1,j,m,n) + dfs(i,j-1,m,n);
    77. //     }
    78. // }
    79.  
    80.

    5、拆分问题: 难点—寻找递推关系，有哪些拆分情况？

    343. 整数拆分：一个正整数 n ，将其拆分为 k 个 正整数 的和，使所有整数的乘积最大化

    96. 不同的二叉搜索树: 由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种

    1. class Solution {
    2.     public int integerBreak(int n) {
    3.         int[] dp = new int[n+1];//从0-n的所有最大拆分乘积
    4.         dp[2] = 1;
    5.         for(int i = 3; i< n+1;i++){ //计算从0-n的所有最大拆分乘积
    6.             for(int j = i-1; j>= 1; j--){
    7.                 dp[i] = Math.max(j*(i-j),dp[i]);
    8.                 dp[i] = Math.max(j*dp[i-j],dp[i]);//与当前已知乘积比较，取最大值
    9.                 //拆分成两个j*(i-j)
    10.                 //拆分成多个数 j*dp[i-j]
    11.             }
    12.         }
    13.         return dp[n];
    14.     }
    15. }
    16.  
    17. //96. 不同的二叉搜索树
    18. class Solution {
    19.     // 二叉搜索树：左小右大
    20.     // 有n节点，依次左右根节点，计算对应的二叉搜索树种类数，相加
    21.     // 每个节点的二叉搜索树种类数 = 左子树的种类数*右子树的种类数    排列
    22.     public int numTrees(int n) {
    23.         int[] dp = new int[n+1];
    24.         dp[0] = 1;
    25.         dp[1] = 1;
    26.         for(int i = 2; i <= n; i++){  //总节点数
    27.            for(int j = 1; j <= i; j++){ //根节点的值:节点值从 1 到 n 互不相同
    28.                 dp[i] += dp[j-1] * dp[i-j];
    29.            }
    30.         }
    31.         return dp[n];
    32.     }
    33. }

    6、背包问题：解决方法

    01背包：取与不取，每件物品只能用一次。物品在外由小到大、背包在内由大到小

    完全背包：取几个（0-N），每件物品可用无数次。背包物品的遍历嵌套顺序均可，都是小到大

    如果求组合数就是 外层for循环遍历物品，内层for遍历背包。

    如果求排列数就是 外层for遍历背包，内层for循环遍历物品。

    多重背包：不同物品数量不同。 1.将物品按数量展开成01背包，通过01背包2维遍历求解；2.物品在外由小到大、背包在内由大到小、物品数量由小到大。3维for遍历。

    分组背包：按组进行选择，每组只能用一次

    • 动态规划：取与不取，改变状态值取最大价值
    • 二维dp数组：
      • 定义数据矩阵：dp[i][j] : i 表示物品，j 表示背包容量
      • 递归公式：背包余量足够时：dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])，不足则保持前一状态：dp[i - 1][j]。
      • 初始化：背包容量j为0，价值总和一定为0，即dp[i][0] = 0。背包可放入编号0的物品，则dp[0][j] = value[0]; 背包容量比编号0的物品重量还小，背包不能容纳任何物品，总价值为0, 即dp[0][j] = 0。并保证其他dp元素的初始值不影响 取最大值的运算，即取整数最小值或0；
      • 遍历顺序：物体 和 背包 均正序遍历
    • 一维dp数组：  空间复杂度更低，简洁
      • 定义数据矩阵：dp[j] :j 表示背包容量
      • 递归公式：背包余量足够时：dp[j] = max(dp[j], dp[j - weight[i]] + value[i])，不足则保持前一状态：dp[j] ,不变。
      • 初始化：背包容量j为0，价值总和一定为0，即dp[0] = 0。
      • 遍历顺序：先正序遍历物品、在遍历背包容量，且背包容量一定是要倒序遍历，需要保证左边的值仍然是上一层的，从右向左覆盖。即保证物品i只被放入一次，只要当前背包余量容量可以放入该物品便放入
    • 回溯法（即暴力解法）寻找所有状态，则n个物品取或不取，对应的时间复杂度就是$o(2^n)$

    背包递推公式：

    • 能否能装满背包（或者最多装多少）：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]); dp总容量
    • 装满背包有几种方法：dp[j] += dp[j - nums[i]] ；dp方法数
    • 背包装满最大价值：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]); dp总价值
    • 装满背包所有物品的最小个数：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);  dp元素数量

    示例：

    1. 来自https://www.programmercarl.com/
    2. public static void main(String[] args) {
    3.         int[] weight = {1, 3, 4};
    4.         int[] value = {15, 20, 30};
    5.         int bagsize = 4;
    6.         testweightbagproblem(weight, value, bagsize);
    7.     }
    8.  
    9. //一维dp
    10.     public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
    11.         int wLen = weight.length;
    12.         //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
    13.         int[] dp = new int[bagWeight + 1];
    14.         //遍历顺序：先遍历物品，再遍历背包容量
    15.         for (int i = 0; i < wLen; i++){
    16.             for (int j = bagWeight; j >= weight[i]; j--){
    17.                 dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
    18.             }
    19.         }
    20.     }
    21.  
    22. //二维dp
    23.     public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
    24.         int wlen = weight.length, value0 = 0;
    25.         //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
    26.         int[][] dp = new int[wlen + 1][bagsize + 1];
    27.         //初始化：背包容量为0时，能获得的价值都为0
    28.         for (int i = 0; i <= wlen; i++){
    29.             dp[i][0] = value0;
    30.         }
    31.         //遍历顺序：先遍历物品，再遍历背包容量
    32.         for (int i = 1; i <= wlen; i++){
    33.             for (int j = 1; j <= bagsize; j++){
    34.                 if (j < weight[i - 1]){
    35.                     dp[i][j] = dp[i - 1][j];
    36.                 }else{
    37.                     dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
    38.                 }
    39.             }
    40.         }
    41.         //打印dp数组
    42.         for (int i = 0; i <= wlen; i++){
    43.             for (int j = 0; j <= bagsize; j++){
    44.                 System.out.print(dp[i][j] + " ");
    45.             }
    46.             System.out.print("\n");
    47.         }
    48.     }

    背包 例题：

    6.1 成对/分成两个子集：求和/2，使得各子集趋近目标值（背包总含量），进行动态规划

    416. 分割等和子集：将数组分割成两个子集，使得两个子集的元素和相等。

    1049. 最后一块石头的重量 II：对一组石头进行对消粉碎，返回此石头 最小的可能重量

    1. 416. 分割等和子集
    2. class Solution {
    3.     public boolean canPartition(int[] nums) {
    4.         int sum = 0;
    5.         int target = 0;
    6.         for(int i = 0; i< nums.length; i++){
    7.             sum += nums[i];
    8.         }
    9.         if(sum % 2 != 0) return false;//和为奇数不可拆分
    10.         target = sum/2;//分割成两个子集,两个子集的元素和相等
    11.         // 0-1背包
    12.         int[] dp = new int[target+1];
    13.         dp[0] = 0;
    14.         for(int i = 0; i< nums.length; i++){
    15.             for(int j = target; j >= nums[i]; j--){
    16.                 dp[j] = Math.max(dp[j], dp[j-nums[i]]+nums[i]);
    17.             }
    18.         }
    19.         //若存在一个子集的和值 = 总和的一半，剩余子集的和值也= 总和一半，满足题意
    20.         return dp[target] == target;
    21.     }
    22. }
    23.  
    24. 1049. 最后一块石头的重量 II
    25. class Solution {
    26.     // 最小差值，最多只会剩下一块 石头
    27.     // 不限制粉碎次数，则 只要将石头分成两份，使得两份的差值尽可能小，即越接近总重/2 差值越小
    28.     public int lastStoneWeightII(int[] stones) {
    29.         int sum = 0;
    30.         for(int i = 0; i< stones.length; i++){
    31.             sum += stones[i];
    32.         }
    33.         int target = sum/2;
    34.         int[] dp = new int[target+1];
    35.         dp[0] = 0;
    36.         for(int i = 0; i< stones.length; i++){
    37.             for(int j = target; j >= stones[i]; j--){
    38.                 dp[j] = Math.max(dp[j], dp[j-stones[i]]+stones[i]);
    39.             }
    40.         }
    41.         return sum-dp[target]-dp[target];//sum-dp[target]表示另一集合的总重量
    42.     }
    43. }

    6.2 组合问题: 求组合个数：动态规划，求装满背包有几种方法，一般公式都是：dp[j] += dp[j - nums[i]]； 求所有组合列表：回溯算法

    1. 动态规划
    2. class Solution {
    3.     //向数组中的每个整数前添加 '+' 或 '-',即分成两组，一组取正值，一组取负值
    4.     // a-b = target a+b = sum ,a = (sum+target)/2
    5.     //返回  运算结果等于 target 的不同 表达式 的数目。
    6.     // 装满有几种方法: 组合问题  dp[j] += dp[j - nums[i]] dp[j]中存储的是装满j容量的方法数
    7.     //当前和的组成方法数 = 放入当前值后，和-当前值 的组成方法数
    8.     public int findTargetSumWays(int[] nums, int target) {
    9.        int sum = 0;
    10.        for(int i = 0; i< nums.length; i++){
    11.            sum += nums[i];//nums[i]全》=0
    12.        }
    13.        if(sum < Math.abs(target)) return 0;//-1000 <= target <= 1000
    14.        if( (sum+target) % 2 != 0) return 0;
    15.        int[] dp = new int[(sum+target)/2+1]; //存放 当前容积有多少种存放方法
    16.        dp[0] = 1;
    17.        for(int i = 0; i< nums.length; i++){//依次不同大小的背包中放入物品
    18.            for(int j = (sum+target)/2; j >= nums[i]; j--){
    19.                dp[j] += dp[j-nums[i]];
    20.            }
    21.        }
    22.         return dp[(sum+target)/2];
    23.     }
    24. }

    6.3 二维的01背包：即需要满足两个条件

    474. 一和零：找出并返回 二进制字符串数组 strs 的最大子集的长度，该子集中 最 有 m个 0和 n个 1 。

    1. class Solution {
    2.     //该子集中 最多 有 m 个 0 和 n 个 1 。
    3.     //找出并返回 strs 的最大子集的长度
    4.     public int findMaxForm(String[] strs, int m, int n) {
    5.         int[][] dp = new int[m+1][n+1];//各条件下最大子集的长度
    6.         for(String s:strs){
    7.             int zeronum = 0, onenum = 0;
    8.             for(int i = 0; i< s.length(); i++){
    9.                 if(s.charAt(i) == '0') {
    10.                     zeronum ++;
    11.                 }else{
    12.                     onenum++;
    13.                 }
    14.             }
    15.             //01背包，每个元素：放与不放，不放原值dp[i][j],放1+dp[i-zeronum][j-onenum];
    16.             for(int i = m; i >= zeronum; i--){
    17.                 for(int j = n; j >= onenum; j--){
    18.                     dp[i][j] = Math.max(dp[i][j], 1+dp[i-zeronum][j-onenum]);
    19.                 }
    20.             }
    21.         }
    22.         return dp[m][n];
    23.     }
    24. }

    6.4 完全背包：物品可多次添加，嵌套顺序均可，小到大（遍历顺序不同，01背包：先物品，在背包大到小）

    • 01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次。二维dp两个for循环嵌套顺序同样无所谓, 一维先物品在背包
    • 完全背包的物品是可以添加多次的，所以要从小到大去遍历，两个for循环嵌套顺序无所谓
    1. // 先遍历物品，再遍历背包
    2. for(int i = 0; i < weight.size(); i++) { // 遍历物品
    3.     for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
    4.         dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
    5.  
    6.     }
    7. }

    6.5 求装满背包有几种方案：

    • 如果求组合数就是外层for循环遍历物品，内层for遍历背包。确保物品存取顺序不会颠倒。
    • 如果求排列数就是外层for遍历背包，内层for循环遍历物品。

    518. 零钱兑换 II: 返回可以凑成总金额的硬币组合数

    377. 组合总和 Ⅳ：从 nums 中找出并返回总和为 target 的元素组合的个数。顺序不同的序列被视作不同的组合 == 排列数

    322. 零钱兑换：最少的硬币个数 ，最少元素数

    279. 完全平方数：返回 和为 n 的完全平方数的最少数量 ，最少元素数

    139. 单词拆分：判断是否可以利用字典中出现的单词拼接出 s。判断是否可以装满背包

    1. 求组合数
    2. 518. 零钱兑换 II
    3. class Solution {
    4.     public int change(int amount, int[] coins) {
    5.         int[] dp = new int[amount+1];
    6.         dp[0] = 1;
    7.         for(int i = 0; i< coins.length; i++){
    8.             for(int j = coins[i]; j<= amount; j++){
    9.                 dp[j] += dp[j-coins[i]];
    10.             }
    11.         }
    12.         return dp[amount];
    13.     }
    14. }
    15.  
    16.  
    17. 求排列数
    18. 377. 组合总和 Ⅳ
    19. class Solution {
    20.     //从 nums 中找出并返回总和为 target 的元素组合的个数。
    21.     //顺序不同的序列被视作不同的组合。
    22.     public int combinationSum4(int[] nums, int target) {
    23.         int[] dp = new int[target+1];
    24.         dp[0] = 1;//和为0 的组合数：1
    25.         for(int i= 0; i <= target; i++){
    26.             for(int j = 0; j < nums.length; j++){
    27.                if(i >= nums[j]){
    28.                     dp[i] += dp[i-nums[j]];
    29.                }
    30.             }
    31.         }
    32.         return dp[target];
    33.     }
    34. }
    35.  
    36. 322. 零钱兑换：最少的硬币个数
    37. class Solution {
    38.     //计算并返回可以凑成总金额所需的 最少的硬币个数, 无则返回-1 
    39.     //每种硬币的数量是无限的。  完全背包, 元素数量问题：组合排列都可以
    40.     public int coinChange(int[] coins, int amount) {
    41.         if(coins.length == 1 && amount % coins[0] != 0) return -1;//无法构成
    42.         int[] dp = new int[amount+1];// 存放凑成各金额所需的 最少的硬币个数
    43.         Arrays.fill(dp,Integer.MAX_VALUE);
    44.         dp[0] = 0;
    45.         for(int i = 0; i < coins.length ; i++){
    46.             for(int j = coins[i]; j <= amount; j++){
    47.                 if(dp[j-coins[i]] != Integer.MAX_VALUE){
    48.                     dp[j] = Math.min(dp[j-coins[i]]+1,dp[j]);   
    49.                 }
    50.             }
    51.         }
    52.         return dp[amount] == Integer.MAX_VALUE? -1: dp[amount];
    53.     }
    54. }
    55.  
    56.  
    57. 279. 完全平方数: 求元素最少个数
    58. class Solution {
    59. //返回 和为 n 的完全平方数的最少数量 。
    60. //完全平方数 是一个整数，其值等于另一个整数的平方,eg:1、4、9 和 16
    61. //可重复选取：完全背包
    62.     public int numSquares(int n) {
    63.         int[] dp = new int[n+1]; //组成和为n的完全平方数的最小数量
    64.         Arrays.fill(dp, Integer.MAX_VALUE);
    65.         dp[0] = 0;
    66.         //先背包，后物品
    67.         // for(int i = 1; i <= n; i++){
    68.         //     for(int j = 1; j*j <= i;j++){
    69.         //         if(dp[i-j*j] != Integer.MAX_VALUE){
    70.         //             dp[i] = Math.min(dp[i], dp[i-j*j]+1);
    71.         //         }
    72.         //     }
    73.         // }
    74.  
    75.         // 先物品，后背包
    76.         for(int i = 0; i <= Math.sqrt(n); i++){
    77.             for(int j = i*i; j <= n; j++){
    78.                 if(dp[j - i*i] != Integer.MAX_VALUE){
    79.                     dp[j] = Math.min(dp[j - i*i] + 1, dp[j]);
    80.                 }
    81.             }
    82.         }
    83.         return dp[n] == Integer.MAX_VALUE? -1:dp[n];
    84.     }
    85. }
    86.  
    87.  
    88. 139. 单词拆分:s是否可以装满背包
    89. // class Solution {
    90. //     //不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。 即：完全背包
    91. //     //判断是否可以利用字典wordDict中出现的单词拼接出 s 
    92. //     //s:背包  wordDict：物品
    93. //     //递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
    94. //     public boolean wordBreak(String s, List wordDict) {
    95. //         boolean[] dp = new boolean[s.length()+1];//存放，当前位置之前的全部元素是否已可由字典组成。
    96. //         dp[0] = true;//0下标表示没有元素null
    97. //         for(int i = 1; i <= s.length(); i++){
    98. //             for(int j = 0; j < i; j++){//截取字符串，判断是否存在字典中
    99. //                 String str = s.substring(j,i);
    100. //                 if(wordDict.contains(str) && dp[j] == true){
    101. //                     dp[i] = true;
    102. //                 }
    103. //             }
    104. //         }
    105. //         return dp[s.length()];
    106. //     }
    107. // }
    108.  
    109. // 回溯法+记忆化
    110. class Solution {
    111.     int[] flag ;
    112.     public boolean wordBreak(String s, List wordDict) {
    113.        flag = new int[s.length()];
    114.        return backtracking(s,0,wordDict);
    115.     }
    116.  
    117.     public boolean backtracking(String s, int index, List wordDict){
    118.         if(index == s.length()){
    119.             return true;//已经寻找结束，前面的已完全匹配
    120.         }
    121.         if(flag[index] == -1){
    122.             return false;//flag中元素表示，从index开始向后匹配能否匹配成功，不能则直接结束
    123.         }
    124.         for(int i = index; i < s.length(); i++){
    125.             String str = s.substring(index,i+1);//截取子字符串，左闭右开
    126.             if(wordDict.contains(str)){
    127.                  boolean res = backtracking(s, i+1, wordDict);
    128.                 if(res) return true;
    129.             }
    130.         }
    131.         //到这,表示以改坐标为起点，匹配不成功，标记并返回
    132.         flag[index] = -1;
    133.         return false;
    134.     }
    135.     
    136. }

    7、不同的数据结构类型，如何进行动态规划

    198. 打家劫舍：队列排列，两间相邻的房屋不能同时进入，求可偷窃到的最高金额。 Math.max(dp[i-2]+nums[i], dp[i-1])，偷、不偷，取较大值

    213. 打家劫舍 II：环状排列，两间相邻的房屋不能同时进入+首尾房间紧挨着。首尾不能同时可选，分两种情况：头可选、尾可选 ，分别计算 取两者的较大值

    337. 打家劫舍 III：二叉树排列，一个入口，每个房子有且仅有一个父房子，两间直接相连的房屋不能同时进入。树状结构：后序遍历 + 二维数组标记左右节点状态与值，根据父节点状态取值

    1. 198. 打家劫舍
    2. class Solution {
    3.     //不可取 两间相邻的元素,所以每次至少走2步
    4.     //偷窃到的最高金额。
    5.     public int rob(int[] nums) {
    6.         if(nums.length == 1) return nums[0];
    7.         int[] dp = new int[nums.length];//存放总金额
    8.         dp[0] = nums[0];//偷时金额为0
    9.         dp[1] = Math.max(nums[0],nums[1]);
    10.         //影响dp[i]的因素是，i房屋偷不偷，
    11.         //偷dp[i] = nums[i]+dp[i-2],i+1不可偷;不偷，dp[i] = dp[i-1]，i+1可偷;
    12.         for(int i = 2; i < nums.length; i++){
    13.             dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);
    14.         }
    15.         return dp[nums.length-1];
    16.     }
    17. }
    18.  
    19. 213. 打家劫舍 II
    20. class Solution {
    21.     //所有的房屋都 围成一圈 第一个房屋和最后一个房屋是紧挨着的:不能同时可取 分两种情况考虑
    22.     //两间相邻的房屋不能同时进入
    23.     //求偷窃到的最高金额 dp
    24.     public int rob(int[] nums) {
    25.         if(nums.length == 1) return nums[0];
    26.         int res1 = robRange(nums, 0, nums.length-1);//考虑头元素，不取尾
    27.         int res2 = robRange(nums, 1, nums.length);//考虑尾元素  ，不取头
    28.         return Math.max(res1, res2);
    29.     }
    30.  
    31.     public int robRange(int[] nums, int start, int end){//左闭右开
    32.         int[] dp = new int[nums.length];
    33.         dp[start] = nums[start];
    34.         dp[start+1] = Math.max(nums[start],nums[start+1]);
    35.         for(int i = start+2; i< end; i++){
    36.             dp[i] = Math.max(dp[i-2]+nums[i], dp[i-1]);//第i个房间偷不偷
    37.         }
    38.         return dp[end-1];
    39.     }
    40. }
    41.  
    42.  
    43. 337. 打家劫舍 III
    44. //从叶子结点开始遍历,后序遍历
    45. // 当前节点i 偷不偷，偷，i-2层的数组和，左左，左右，右左，右右+value, 不偷，dp[i] = dp[i].left+dp[i].right
    46. class Solution {
    47.     Map map = new HashMap<>();//记录每个节点的最大金额，没有记录每个节点的状态（偷没偷）
    48.     public int rob(TreeNode root) {
    49.         if(root == null) return 0;
    50.         if(map.containsKey(root)) return map.get(root);
    51.         //偷root节点
    52.         int res1 = root.val;
    53.         if(root.left != null){
    54.             res1 += rob(root.left.left) + rob(root.left.right);
    55.         }
    56.         if(root.right != null){
    57.             res1 += rob(root.right.left) + rob(root.right.right);
    58.         }
    59.  
    60.         //不偷root节点
    61.         int res2 = rob(root.left) + rob(root.right);
    62.         int val = Math.max(res1,res2);
    63.         map.put(root,val);
    64.         return val;
    65.     }
    66. }
    67. // 记录每个节点的状态（偷 / 没偷）以及对应最大金额，返回值为int[2]类型;
    68.     // 不偷：Max(左孩子不偷，左孩子偷) + Max(又孩子不偷，右孩子偷)
    69.     // root[0] = Math.max(rob(root.left)[0], rob(root.left)[1]) +
    70.     // Math.max(rob(root.right)[0], rob(root.right)[1])
    71.     // 偷：左孩子不偷+ 右孩子不偷 + 当前节点偷
    72.     // root[1] = rob(root.left)[0] + rob(root.right)[0] + root.val;
    73. class Solution {
    74.     public int rob(TreeNode root) {
    75.         int[] res = robTree(root);
    76.         return Math.max(res[0], res[1]);//0没偷，1偷了
    77.     }
    78.     public int[] robTree(TreeNode root){
    79.         if(root == null) return new int[]{0,0};//相当于初始化
    80.         int[] res = new int[2];
    81.         int[] left = robTree(root.left);
    82.         int[] right = robTree(root.right);//不要在下面的表达式中直接写，会多次重复运算
    83.         res[0] = 0 + Math.max(left[0], left[1])
    84.                 + Math.max(right[0], right[1]);
    85.         res[1] = root.val +left[0] +right[0];
    86.         return res;        
    87.     }
    88. }

    8、股票获取最大收益：写出所有状态下   的所有情况下的收益取最大值，用数组存储

    • dp[i][0] 表示第i天持有股票所得现金。
    • dp[i][1] 表示第i天不持有股票所得最多现金

    121. 买卖股票的最佳时机：只能选择某天买进，之后的某天卖出，取最大利润

    股票全程只能买卖一次：(贪心：左最低买入，右最高卖出）两种状态

    • 第i天不持有股票：1、之前卖出dp[i-1][1]  2、当天卖出则第i-1天持有dp[i-1][0]+price[i]
    • 第i天持有股票：1、之前也持有dp[i-1][0]  2、当天持有的 -price[i]

    股票全程能买卖多次：（贪心：取所有正收益的和）两种状态：延续，改变状态

    • 第i天不持有股票：1、之前卖出dp[i-1][1]  2、当天卖出则第i-1天持有dp[i-1][0]+price[i]
    • 第i天持有股票：1、之前也持有dp[i-1][0]  2、当天持有的，之前的盈利(即i-1天不持有）减支出 dp[i-1][1]-price[i]

    股票最多可以买卖两次：5种状态

    股票最多可以买卖K次：2*k+1种状态，即0:无操作，奇数：买入 -prices，偶数：卖出 +prices

    309. 最佳买卖股票时机含冷冻期：买入时  跳过冷冻期时间取之前卖出收益

    714. 买卖股票的最佳时机含手续费：买入时有手续费：买入时 当前收益-股价-手续费

    1. 121. 买卖股票的最佳时机
    2. class Solution {
    3.     //贪心算法，取最小买入价格，最高收益，效率更高
    4.     public int maxProfit(int[] prices) {
    5.         int min = Integer.MAX_VALUE;
    6.         int res = 0;//记录最大利润
    7.         for(int i = 0; i< prices.length; i++){
    8.             min = Math.min(min,prices[i]);//取最低买入金额
    9.             res = Math.max(res,prices[i] - min);//之前卖出，和 当前卖出 取较大值
    10.         }
    11.         return res;
    12.     }
    13. }
    14.  
    15. class Solution {
    16.     //动态规划，每日更新
    17.     public int maxProfit(int[] prices) {
    18.         int[] dp = new int[2];//0:持有（当天买入、之前买入） ，1:不持有（卖出，之前卖出）
    19.         //dp存放获得最大收益
    20.         dp[0] = -prices[0];
    21.         dp[1] = 0;
    22.         for(int i = 1; i < prices.length; i++){
    23.             dp[0] = Math.max(dp[0],-prices[i]);
    24.             dp[1] = Math.max(dp[1], prices[i]+dp[0]);//当天卖出，前一天一定是持有的
    25.         }
    26.         return  dp[1];//卖出，收益更高
    27.     }
    28. }
    29.  
    30.  
    31. 122. 买卖股票的最佳时机 II
    32. class Solution {
    33.     public int maxProfit(int[] prices) {
    34.         int len = prices.length;
    35.         int[][] dp = new int[len][2];//0持有，1不持有
    36.         dp[0][0] = -prices[0];
    37.         dp[0][1] = 0;
    38.         for(int i = 1; i< len; i++){
    39.             dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]);
    40.             dp[i][1] = Math.max(prices[i]+dp[i-1][0], dp[i-1][1]);
    41.         }
    42.         return dp[len-1][1];
    43.         
    44.     }
    45. }
    46.  
    47. 123. 买卖股票的最佳时机 III
    48. class Solution {
    49.     //你最多可以完成 两笔 交易。
    50.     public int maxProfit(int[] prices) {
    51.         int[] dp = new int[5];//有5种状态下的收益
    52.         dp[0] = 0;//无操作
    53.         dp[1] = -prices[0];//第一次买入
    54.         dp[2] = 0;//第一次卖出
    55.         dp[3] = -prices[0];//第二次买入
    56.         dp[4] = 0;//第二次卖出
    57.         for(int i = 1; i < prices.length; i++){
    58.             //后面的状态需要前面的值，从4-》0更新状态收益
    59.             dp[4] = Math.max(dp[4], dp[3]+prices[i]);//延续，或当天改变状态
    60.             dp[3] = Math.max(dp[3], dp[2]-prices[i]);
    61.             dp[2] = Math.max(dp[2], dp[1]+prices[i]);
    62.             dp[1] = Math.max(dp[1], dp[0]-prices[i]);
    63.             dp[0] = 0;
    64.         }
    65.         return dp[4];//最后的卖出状态收益更高
    66.     }
    67. }
    68.  
    69. 188. 买卖股票的最佳时机 IV:最多可以完成 k 笔交易。
    70. class Solution {
    71.     public int maxProfit(int k, int[] prices) {
    72.         if(prices == null || prices.length == 0) return 0;
    73.         int[] dp = new int[2*k+1];
    74.         dp[0] = 0;
    75.         for(int j = 1; j < 2*k+1; j = j+2){
    76.             dp[j] = -prices[0];
    77.         }
    78.         for(int i = 1; i < prices.length; i++){
    79.             for(int j = 2*k; j > 0; j--){
    80.                 int sign = (j%2==0? 1:-1);//奇数买入，偶数卖出
    81.                 dp[j] = Math.max(dp[j],dp[j-1]+sign*prices[i]);
    82.             }
    83.         }
    84.         return dp[2*k];
    85.     }
    86. }
    87.  
    88.  
    89. 309.最佳买卖股票时机含冷冻期
    90. class Solution {
    91.     //卖出股票后，你无法在第二天买入股票 (即冷冻期为 1 天)。
    92.     //尽可能地完成更多的交易（多次买卖一支股票）
    93.     public int maxProfit(int[] prices) {
    94.         if(prices == null || prices.length <= 1) return 0;
    95.         //状态：0买入（第i天买入的话之前的收益为i-2天的卖出状态的收益），1卖出
    96.         int[][] dp = new int[prices.length][2];
    97.         dp[0][0] = -prices[0];
    98.         dp[0][1] = 0;
    99.         dp[1][0] = Math.max(dp[0][0],-prices[1]);
    100.         dp[1][1] = Math.max(prices[1]+dp[0][0],0);
    101.         for(int i = 2; i < prices.length; i++){
    102.             dp[i][0] = Math.max(dp[i-1][0], dp[i-2][1]-prices[i]);//买入状态
    103.             dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]+prices[i]);//卖出状态
    104.         }
    105.         return dp[prices.length-1][1];
    106.     }
    107. }
    108.  
    109. 714. 买卖股票的最佳时机含手续费
    110. class Solution {
    111.     public int maxProfit(int[] prices, int fee) {
    112.         // int[][] dp = new int[prices.length][2];//0买入，1卖出
    113.         // dp[0][0] = -prices[0]-fee;
    114.         // dp[0][1] = 0;
    115.         // for(int i = 1; i< prices.length; i++){
    116.         //     dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1]-prices[i]-fee);
    117.         //     dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0]+prices[i]);
    118.         // }
    119.         // return dp[prices.length-1][1];
    120.         int[] dp = new int[2];//0买入，1卖出
    121.         dp[0] = -prices[0]-fee;
    122.         dp[1] = 0;
    123.         for(int i = 1; i< prices.length; i++){
    124.             dp[0] = Math.max(dp[0], dp[1]-prices[i]-fee);
    125.             dp[1] = Math.max(dp[1], dp[0]+prices[i]);
    126.         }
    127.         return dp[1];
    128.     }
    129. }

    9、子序列问题：单一维度

    • dp[i]  存储到当前值满足条件的最大长度、个数，取dp中的最大值
    • dp[i][j]：以i-1为结尾的s子序列中出现以j-1为结尾的t的个数为dp[i][j]。根据变化条件（一般为当前相应值是否相等）相等则不变，取斜上角值（二维）、前一个值（一维）+增量；不等 取周边最大值最小值+增量

    300. 最长严格递增子序列：j = 0~i     nums[i] > nums[j]则 dp[i] = max(dp[i], dp[j] + 1);即长度+1674. 最长连续递增序列：nums[i]>nums[i-1] 则 dp[i] = Math.max(dp[i],dp[i-1]+1)

    53. 最大连续子数组和:  贪心（只取连续子列的正和，否则为0以当前元素从新开始）、动态规划（求当前位置i的最大连续子数组和：dp[i] = Math.max(dp[i-1]+nums[i], nums[i]) 取所有dp的最大值）

    1. 300. 最长递增子序列
    2. class Solution {
    3.     public int lengthOfLIS(int[] nums) {
    4.         if(nums == null || nums.length == 0)  return 0;
    5.         int[] dp = new int[nums.length];//记录以nums[i]为结尾的子序列的最长递增子序列的长度
    6.         int res = 1;
    7.         Arrays.fill(dp,1);//递增子序列的最小长度为1
    8.         for(int i = 1; i< nums.length; i++){
    9.             for(int j = 0; j< i; j++){
    10.                 if(nums[i] > nums[j]){
    11.                     dp[i] = Math.max(dp[i], dp[j]+1);//当前数值为结尾的递增子序列的最大长度+1
    12.                 }
    13.             }
    14.             res = Math.max(dp[i],res);//取最大值
    15.         }
    16.         return res;
    17.     }
    18. }
    19.  
    20.  
    21. 674. 最长连续递增序列
    22. class Solution {
    23.     //最长且 连续递增的子序列
    24.     public int findLengthOfLCIS(int[] nums) {
    25.         //动态规划
    26.         // int[] dp = new int[nums.length];
    27.         // int res = 1;
    28.         // Arrays.fill(dp,1);
    29.         // for(int i = 1; i< nums.length; i++){
    30.         //     if(nums[i]>nums[i-1]){//连续
    31.         //         dp[i] = Math.max(dp[i],dp[i-1]+1);//存储到当前值的最大长度
    32.         //     }
    33.         //     res = Math.max(dp[i],res);
    34.         // }
    35.         // return res;
    36.  
    37.         //贪心算法，更快
    38.         int count = 1; //记录递增长度
    39.         int res = 1; //记录最大长度
    40.         for(int i = 1; i< nums.length; i++){
    41.             if(nums[i]>nums[i-1]){
    42.                 count++;
    43.             }else{
    44.                 count = 1;
    45.             }
    46.             res = Math.max(res,count);
    47.         }
    48.         return res;
    49.     }
    50. }
    51.  
    52.  
    53.  
    54. 53. 最大子数组和
    55. class Solution {
    56.     public int maxSubArray(int[] nums) {
    57.         // 贪心算法，支取正和区间
    58.         // if(nums.length == 1) return nums[0];
    59.         // int res = Integer.MIN_VALUE;
    60.         // int sum = 0;
    61.         // for(int i= 0; i< nums.length; i++){
    62.         //     if(sum < 0){
    63.         //         sum = 0;//之前元素的和为负数，则不取
    64.         //     }
    65.         //     sum += nums[i];
    66.         //     res = Math.max(sum,res);
    67.         // }
    68.         // return res;
    69.  
    70.         //动态规划  dp[i] 0-i的子序列的最大和
    71.         int[] dp = new int[nums.length];
    72.         dp[0] = nums[0];
    73.         int res = dp[0];
    74.         for(int i=1; i< nums.length; i++){
    75.             dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);//看之前取的元素和是正还是负
    76.             res = res > dp[i]? res: dp[i];//取所有最大和的最大值
    77.         }
    78.         return res;
    79.     }
    80. }
    81.

    10. 子序列问题：公共序列（个数），或变为相等字符串（操作数），二维

    重点：1. dp矩阵的定义，2. 当前元素存在的几种情况和相应的操作  对dp元素值的影响

    718. 最长重复子数组: 求两个数组的最大重复子序列长度，二维遍历比较，相同+1。

    • 二维dp记录每个位置上可取的最大公共子序列长度。行：nums1元素i，列：nums2元素j，对应i/j元素相同：dp[i+1][j+1] = dp[i][j]+1;
    • 一维dp :类似背包，一个数组为物品i，另一个为背包容器j，判断背包中是否含有该物品，相同则dp[i] = dp[j-1]+1，不同则dp[i] = 0;

    1143. 最长公共子序列: 求两个字符串的 最大公共子序列长度（即相对位置保持一致），二维遍历，相同则+1（dp[i-1][j-1]+1）,不同取相邻位置的较大值max(dp[i-1][j],dp[i][j-1]).

    1035. 不相交的线:  连接两个数组中的相同元素，保证连线之间不相交，求绘制的最大连线数 = 元素的相对位置保持一致，求最大公共子序列长度。与上题一致。

    392. 判断子序列: 判断 s 是否为 t 的子序列， 即s和t的最大公共子序列的长度是否等于s的长度。（直接向后查询所需元素，或者双指针法比较元素 均可解出）

    1. if (s[i - 1] == t[j - 1]){
    2.     dp[i][j] = dp[i - 1][j - 1] + 1;  //t中找到了一个字符在s中也出现了
    3.  
    4. }else {
    5.     dp[i][j] = dp[i][j - 1];//相当于t要删除元素，继续匹配
    6. }

    115. 不同的子序列:计算在 s 的子序列中 t 出现的个数。(元素的相对位置相同）。

    判断当前元素是否对应相等，相等叠加;，不等保持 ;

    1. if (s[i - 1] == t[j - 1]) {
    2.     dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
    3.     //相等 时  = 当前包含s[i-1]元素时+ 不包含s[i-1]元素时 t(0-j-1子序列)的出现个数 
    4. } else {
    5.     dp[i][j] = dp[i - 1][j];
    6.     //不相等时  = 不包含s[i-1]元素时 t(0-j-1子序列)的出现个数
    7. }

    583. 两个字符串的删除操作: 两个字符串只能删除元素，使得 二者相同所需的最小步数。

    对应元素相等，操作数不增加； 不相等，删除w1元素，对应位置操作数的基础上+1，删除w2元素，操作数+1；l两者都删除，操作数+2；

    72. 编辑距离: 对字符串进行插/删除/替换字符操作，变成目标字符串，最少需要多少操作数。

    1. dp[i][j]:表示s1的0~i-1和s2的0~j-1的编辑距离
    2. if (word1[i - 1] == word2[j - 1])
    3.     dp[i][j] = dp[i - 1][j - 1];//不操作
    4. if (word1[i - 1] != word2[j - 1])
    5.     dp[i][j] = dp[i - 1][j] + 1;//增
    6.     dp[i][j] = dp[i][j - 1] + 1;//删
    7.     dp[i][j] = dp[i - 1][j - 1] + 1;//换
    8.    //三种情况中选一个
    9.    //题目要求：最小操作数：取三者最小值
    1. 718. 最长重复子数组
    2. class Solution {
    3.     public int findLength(int[] nums1, int[] nums2) {
    4.         // int[][] dp = new int[nums1.length+1][nums2.length+1];
    5.         // //dp[i][j] 表示nums1 0~i-1处 与nums2 0~j-1处的公共序列长度
    6.         // //dp[i][0] = 0; dp[0][j] = 0;均表示未取值
    7.         // int res = 0;
    8.         // for(int i = 0; i< nums1.length; i++){
    9.         //     for(int j = 0; j< nums2.length; j++){
    10.         //         if(nums1[i] == nums2[j]){
    11.         //             dp[i+1][j+1] = dp[i][j]+1;
    12.         //             res = Math.max(dp[i+1][j+1],res);//保存最大值
    13.         //         }
    14.         //     }
    15.         // }
    16.         // return res;
    17.  
    18.         //将二维变为一维,  向下对角线上元素相等+1
    19.         int[] dp = new int[nums2.length+1];
    20.         int res = 0;
    21.         //类似背包
    22.         for(int i = 0; i < nums1.length; i++){//物品
    23.             for(int j = nums2.length-1; j>=0; j--){//背包  从后向前遍历，避免重复
    24.                 if(nums1[i] == nums2[j]){
    25.                     dp[j+1] = dp[j]+1;               
    26.                 }else{
    27.                     dp[j+1] = 0;//当前数值不相等，表示以当前数值为结尾的序列是不存在公共序列的
    28.                 }
    29.                 res = Math.max(dp[j+1],res);
    30.             }
    31.         }
    32.         return res;
    33.     }
    34. }
    35.  
    36.  
    37.  
    38.  
    39. 1143. 最长公共子序列
    40. class Solution {
    41.     public int longestCommonSubsequence(String text1, String text2) {
    42.         if(text1 == null || text2 == null || text1.length() == 0|| text2.length() == 0){
    43.              return 0;
    44.         }   
    45.         char[] t1 = text1.toCharArray();
    46.         char[] t2 = text2.toCharArray();
    47.  
    48.         //二维dp 
    49.         int[][] dp = new int[t1.length+1][t2.length+1];
    50.         //dp[i][j] : text1的0~i-1的子序列与 text2的0~j-1的子序列  的最大公共子序列的长度
    51.         //第0行、0列均为0， 列text2元素，行text1元素
    52.         for(int i = 1; i <= t1.length; i++){
    53.             for(int j = 1; j<= t2.length; j++){
    54.                 if(t1[i-1] == t2[j-1]){
    55.                     dp[i][j] = dp[i-1][j-1]+1;//相等+1
    56.                 }else{
    57.                     dp[i][j]= Math.max(dp[i-1][j],dp[i][j-1]);//不等取最大值
    58.                 }
    59.             
    60.             }
    61.         }
    62.         return dp[t1.length][t2.length];
    63.         }
    64.     }
    65. }
    66.  
    67.  
    68.  
    69. 392. 判断子序列:判断 s 是否为 t 的子序列。
    70. class Solution {
    71.     public boolean isSubsequence(String s, String t) {
    72.         if(s == null || t == null || s.length() > t.length()){
    73.             return false;
    74.         }//特殊情况判断
    75.         int index = -1;
    76.         for(char c : s.toCharArray()){
    77.             index = t.indexOf(c,index+1);
    78.             if(index == -1) return false;//没找到该元素
    79.         }
    80.         return true;
    81.  
    82.         //双指针法
    83.         int si = 0;
    84.         int ti = 0;
    85.         while(si < s.length() && ti < t.length()){
    86.             if(s.charAt(si) == t.charAt(ti)){
    87.                 si++;
    88.             }//当前元素以匹配，后移指针
    89.             ti++;
    90.         }
    91.         return si == s.length();
    92.  
    93.     //动态规划：s 为 t 的子序列即 s/t最大公共子序列的长度为s的长度
    94.         int[][] dp =  new int[s.length()+1][t.length()+1];
    95.         //dp[i][j] : 表示s的0~i-1 与t的0~j-1的相同子序列的长度
    96.         char[] s1 = s.toCharArray();
    97.         char[] t1 = t.toCharArray();
    98.         for(int i = 1; i <= s.length(); i++){
    99.             for(int j = 1; j <= t.length(); j++){
    100.                 if(s1[i-1] == t1[j-1]){
    101.                     dp[i][j] = dp[i-1][j-1] + 1;
    102.                 }else{
    103.                     dp[i][j] = dp[i][j-1];//dp[i-1][j] 一定比dp[i][j-1]小，因为 t1[j-1]无用
    104.                 }
    105.             }
    106.         }
    107.         return dp[s.length()][t.length()] == s.length();//最大公共子序列的长度为s的长度
    108.         
    109.     }
    110. }
    111.  
    112.  
    113. 115. 不同的子序列:计算在 s 的子序列中 t 出现的个数。(元素的相对位置相同）
    114. class Solution {
    115.     public int numDistinct(String s, String t) {
    116.         int[][] dp = new int[s.length()+1][t.length()+1];
    117.         //dp:在 s 的子序列中 t 出现的个数。dp[0][j] = 0,s为[],不可能包含t
    118.         for(int i = 0; i < s.length(); i++){
    119.             dp[i][0] = 1;//即t为空[]
    120.         }
    121.         char[] s1 = s.toCharArray();
    122.         char[] t1 = t.toCharArray();
    123.         for(int i = 1; i<= s.length(); i++){
    124.             for(int j = 1; j <= t.length(); j++){
    125.                 //延续 或 叠加
    126.                 if(s1[i-1] == t1[j-1]){
    127.                     //相等 = 当前包含s[i-1]元素时+ 不包含s[i-1]元素时 t(0-j-1子序列)的出现个数
    128.                     dp[i][j] = dp[i-1][j-1] + dp[i-1][j];
    129.                 }else{
    130.                     dp[i][j] = dp[i-1][j];//不包含s[i-1]元素时 t(0-j-1子序列)的出现个数
    131.                 }
    132.             }
    133.         }
    134.         return dp[s.length()][t.length()];
    135.     }
    136. }
    137.  
    138.  
    139. 72. 编辑距离
    140. class Solution {
    141.     public int minDistance(String word1, String word2) {
    142.         int l1 = word1.length();
    143.         int l2 = word2.length();
    144.         int[][] dp = new int[l1+1][l2+1];
    145.         char[] w1 = word1.toCharArray();
    146.         char[] w2 = word2.toCharArray();
    147.         //初始化，字符串《-》空集  的操作数 =  元素数
    148.         for(int i = 0; i <= l1; i++){
    149.             dp[i][0] = i;
    150.         }
    151.         for(int j = 0; j <= l2; j++){
    152.             dp[0][j] = j;
    153.         }
    154.         for(int i = 1; i <= l1; i++){
    155.              for(int j = 1; j <= l2; j++){
    156.                  if(w1[i-1] == w2[j-1]){
    157.                      dp[i][j] = dp[i-1][j-1];
    158.                  }else{
    159.                      dp[i][j] = Math.min(Math.min(dp[i-1][j],dp[i][j-1]),dp[i-1][j-1])+1;
    160.                      //dp[i-1][j]+1 :w2添加元素   即添加w1[i-1]元素
    161.                      //dp[i][j-1]+1 : W2删除w2[j-1]元素
    162.                      //dp[i-1][j-1]+1 :w2替换
    163.                  }
    164.              }
    165.         }
    166.         return dp[l1][l2];
    167.     }
    168. }
    169.  
    170. 583. 两个字符串的删除操作
    171. class Solution {
    172.     public int minDistance(String word1, String word2) {
    173.         int l1 = word1.length();
    174.         int l2 = word2.length();
    175.         char[] w1 = word1.toCharArray();
    176.         char[] w2 = word2.toCharArray();
    177.         //方式一：求两个字符串的公共序列长度，再用各自字符串长度- 公共序列长度
    178.         //方式二：直接统计使得当前子序列相等 的最小步数
    179.         int[][] dp = new int[l1+1][l2+1];//子序列相等 的最小步数
    180.         // 要与空集相等的最小步数 = 序列长度
    181.         for(int i = 0; i <= l1; i++){
    182.             dp[i][0] = i;
    183.         }
    184.         for(int j = 1; j <= l2; j++){
    185.             dp[0][j] = j;
    186.         }
    187.         for(int i = 1; i <= l1; i++){
    188.             for(int j = 1; j <= l2; j++){
    189.                 if(w1[i-1] == w2[j-1]){//相等，不操作
    190.                     dp[i][j] = dp[i-1][j-1] ;                
    191.                 }else{//不相等，取当前最小步数
    192.                     dp[i][j] = Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);
    193.                     //删除w1[i-1];删除w2[j-1];两个都删除；
    194.                 }
    195.             }
    196.         }
    197.         return dp[l1][l2];
    198.     }
    199. }

    11、回文字符串的判断、统计

    647. 回文子串：统计并返回这个字符串中 回文子串 的数目，统计dp中为true的单元数

    • dp[i][j]: 字符串i-j位置的序列是否为回文子串，true，false；根据定义：必须 j >= i
      1. if (s[i] == s[j]) {
      2.     if (j - i <= 1) { // 情况一 和 情况二
      3.         //下标相同或者相差为1，该字符串为回文子串
      4.         result++;
      5.         dp[i][j] = true;
      6.     } else if (dp[i + 1][j - 1]) { // 情况三
      7.         //相差> 1，需要判断他们的中间字符串是否是回文的
      8.         result++;
      9.         dp[i][j] = true;
      10.         //当前结果需要已知dp[i + 1][j - 1]，遍历顺序i:下到上，j:左到右
      11.     }
      12. }

    516. 最长回文子序列: 找出其中最长的回文子序列按顺序选择的字符串）

    dp[i][j]: 字符串i-j位置的子序列构成的回文子串的最大长度；；相等：数量+2，不等，取可能情况的最大值

    1. 647. 回文子串
    2. //动态规划
    3. class Solution {
    4.     public int countSubstrings(String s) {
    5.         int len = s.length();
    6.         char[] s1 = s.toCharArray();
    7.         boolean[][] dp = new boolean[len][len];//初始值false
    8.         int count = 0;
    9.         for(int i = len-1; i >= 0; i--){
    10.             for(int j = i; j < len; j++){
    11.                 if(s1[i] == s1[j]){
    12.                      if(j-i <= 1 || dp[i+1][j-1] == true){
    13.                         dp[i][j] = true;
    14.                         count++;
    15.                     }
    16.                 }
    17.             }
    18.         }
    19.         return count;
    20.     }
    21. }
    22.  
    23. //双指针法，以对称中心（1个元素，2个元素）向两侧出发，比较对应元素
    24. class Solution {
    25.     public int countSubstrings(String s) {
    26.         int count = 0;
    27.         char[] s1 = s.toCharArray();
    28.         for(int i = 0; i< s1.length; i++){
    29.             count += extend(i,i,s1);
    30.             count += extend(i,i+1,s1);
    31.         }
    32.         return count;
    33.     }
    34.     public int extend(int i, int j, char[] s){
    35.         int res = 0;
    36.         while(i >= 0 && j < s.length && s[i] == s[j]){//考虑边界
    37.             i--;
    38.             j++;
    39.             res++;
    40.         }
    41.         return res;
    42.     }
    43. }
    44.  
    45. 516. 最长回文子序列: 不改变剩余字符顺序的情况下，删除某些字符
    46. class Solution {
    47.     public int longestPalindromeSubseq(String s) {
    48.         int len  = s.length();
    49.         char[] s1 = s.toCharArray();
    50.         int[][] dp = new int[len][len];//i-j的回文子序列的最长长度
    51.         int res = 0;
    52.         if(s == null || len == 0){
    53.             return res;
    54.         }else{
    55.             res = 1;
    56.         }
    57.         for(int i = 0; i < len; i++){
    58.                 dp[i][i] = 1;//单个元素也是回文
    59.         }
    60.         for(int i = len-1; i >= 0; i--){
    61.             for(int j = i+1; j < len; j++){
    62.                 if(s1[i] == s1[j]){
    63.                     dp[i][j] = dp[i+1][j-1]+2;//i 大到小，j小到大
    64.                 }else{
    65.                     dp[i][j] = Math.max(Math.max(dp[i+1][j],dp[i][j-1]),dp[i+1][j-1]);
    66.                     //不等时，删除左侧元素、还是右侧元素，还是两边都删除
    67.                 }
    68.                 res = Math.max(res, dp[i][j]);
    69.             }
    70.         }
    71.         return res;
    72.     }
    73. }

  • 相关阅读:
    数据库：什么是数据库，有哪些数据库，数据库用来干什么，图导，拓展
    Android Gradle - AGP（Android Gradle Plugin）更新失败，你遇到了吗？
    ESP8266-Arduino编程实例-MQ-7一氧化碳传感器驱动
    Python学习笔记——逻辑判断和循环
    【多式联运】基于帝国企鹅算法、遗传算法、粒子群算法求解多式联运路径优化问题附matlab代码
    【HarmonyOS】鸿蒙中如何获取用户相册图片？photoAccessHelper.PhotoViewPicker
    WPF绘制圆形调色盘
    线性空间、子空间、基、基坐标、过渡矩阵
    大话机器学习准确率(Accuracy)、精确率(Pecision)、召回率(Recall)以及TP、FP、TN、FN
    AB实验求置信区间和p值
  • 原文地址：https://blog.csdn.net/habe33/article/details/126310677