• 确定dp数组（dp table）以及下标的含义
• 确定递推公式
• dp数组如何初始化
• 确定遍历顺序
• 举例推导dp数组

3.常见题型

• 基础类题目
• 背包问题
• 打家劫舍
• 股票问题
• 子序列问题

（1）背包问题

• 01背包问题
  • 有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。
    
    
  • ★dp数组的含义
    01背包的dp数组由两种定义方式，一种是二维dp数组(基础)，另一种是一维dp数组(优化)，这里先掌握二维的。
    dp[i，j]代表从下标为 0 到 i 的物品里任意取，放进容量为 j 的背包，价值总和最大是多少。
    
    
  • 递推公式
    对于一个物品，只有取与不取两种状态，所以dp[i][j]就取决于“不取物品i”和“取了物品i”：
            不取物品 i：不取物品i的最大价值也就是取了0到 i-1物品的最大价值，即dp[i][j]=dp[i-1][j]；
            取了物品 i：取了物品i的最大价值也就是前 i-1 个物品减掉要取的 i 的重量(因为要留出来放物品i)的价值，加上 i 的价值，即dp[i][j]=dp[i-1][j-weight[i]]+value[i]；
    因为题目要求最大价值，所以二者取最大，即dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。
  • 初始化dp
    根据递推公式dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])可以看出，dp[i][j]是由其上边和左边的数据得出来的，所以要对最上行和最左列进行初始化：
            最上行：根据物品0的重量(1)和价值(15)进行初始化。此时应该是
                           
            最左列：因为背包容量为0，所以价值都为0。
    所以dp数组应该初始化为：
            
  • 遍历顺序
    01背包需要两层for循环，一层遍历物品，一层遍历背包容量，那么是先遍历物品，还是先遍历背包呢？
    ——当dp数组定义为二维数组时，先遍历物品和先遍历背包都可以，因为都可以做到通过左边和上边得到当前值。
• ★一维数组解决01背包问题
  上面用了二维数组定义dp数组，通过递推公式dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i])。可以看出，当前数据(i)都是由上一层(i-1)得到的，所以我们可以将上一层数据更新到当前层，这样就从二维降到了一维，相当于只在一行上进行计算，每次都更新这一行。这个一维数组就叫滚动数组。
  • dp数组的含义
    这里有个小技巧，将下标用j表示，这样与二维数组的j代表的意思就一样了，更方便理解与记忆。
    dp[ j ]表示容量为j的背包，所能装的最大价值为dp[j]。
  • 递推公式
    这里与二维数组时的思路是一样的，都是分为取i和不取i：
            不取物品 i：此时这一行就是前i-1个物品在j容量时的最大价值(将上一层的更新了)，所以dp[j]=dp[j]；
            取了物品 i：此时应该是前 i-1 个物品减掉要取的 i 的重量，加上 i 的价值，即dp[j]=dp[j-weight[i]]+value[i]；
    综上取最大值，dp[j] = max(dp[j], dp[j - weight[i]] + value[i])。
  • 初始化
    dp[0]代表容量0的最大价值，所以dp[0]=0。
  • ★遍历顺序
    一维dp的遍历顺序很有讲究，是先遍历物品，再倒序遍历背包容量：

    for(int i = 0; i <= 物品最大编号; i++) { // 遍历物品(★从0开始)
        for(int j = bagWeight; j >= weight[i]; j--) { // 倒序遍历背包容量(★减到weight[i])
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

    （一）为什么要倒序遍历背包容量？
            因为我们在将二维降为一维时，是利用上一层(上一个物品)来推出当前层，并且将上一层更新到当前层，如果正序遍历背包会再计算一次上一层数据，相当于同一物品取了两次。因此倒序遍历是为了保证物品i只被放入一次。
    （二）为什么要先物品再背包？
            因为在遍历容量时一定要倒序遍历，如果先倒序遍历背包，再遍历物品，那么每个dp[j]就只会放入一个物品，即：背包里只放入了一个物品。
    （三）倒序遍历时为什么j要≥weight[i]？
            因为至少要保证背包的容量 j 能把物品 i 放进去。
    （四）为什么 i 要从0开始遍历？
            因为初始化dp[0]时只是物品i在背包容量0的情况。
    

• 完全背包问题
  • 有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
    完全背包和01背包问题唯一的不同就是完全背包每种物品有无数件。
  • 如何做到让每件物品可以使用无数次呢？
    ——在01背包中，将dp数组定义成一维滚动数组时，在遍历顺序上为了保证每件只能用一次，我们选择倒序遍历背包容量。在完全背包中，为了让物品可以使用无数次，只需要改为正序遍历背包容量即可（因为滚动数组是由上一层推出来的，所以正序遍历相当于不断累加）。

    // 先遍历物品，再遍历背包
    for(int i = 0; i < weight.size(); i++) { // 遍历物品
        for(int j = weight[i]; j <= bagWeight ; j++) { // 遍历背包容量
            dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
        }
    }

  • 滚动数组定义的dp的两层for循环可以颠倒吗？
    ——可以颠倒。因为dp[j] 是根据下标 j 之前所对应的dp[j]计算出来的，只要保证下标 j 之前的dp[j]都是经过计算的就可以了。

    //  先遍历背包，在遍历物品
    for(int j = 0; j <= bagWeight; j++) { // 遍历背包容量（j从0开始，因为不知道从哪个物品开始）
        for(int i = 0; i < weight.size(); i++) { // 遍历物品
            if (j - weight[i] >= 0){//j从0开始，为防止下标溢出，要保证j - weight[i] >= 0
                dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
            }
        }
    }

  • 求装满背包有几种方案时，对于结果分为组合数({1，3}和{3，1}算同一种排列)和排列数({1，3}和{3，1}算两种排列)
    ——如果求组合数，就要先遍历物品，再遍历容量。
    ——如果求排列数，就要先遍历容量，再遍历物品。
    

• 多重背包问题

• 思路一：递归。

  public int fib(int n) {
      if(n==0||n==1){
          return n;
      }
      return fib(n-1)+fib(n-2);
  }

• 思路二：dp。这道题常规来说直接用递归做就行了，但也是用来入门dp的一道基础题，可以用来熟悉dp的解题步骤。
  • 确定dp数组及下标含义：dp[ i ] 代表第 i 个斐波那契数；
  • 确定递推公式：这道题简单在递推公式已经给我们了：dp[ i ] = dp[ i-1 ]+dp[ i-2 ]；
  • dp数组的初始化：题目已知第一个那契数是0，第二个那契数是1，即dp[0]=0，dp[1]=1；
  • 确定遍历顺序：从递推公式可以看出，我们需要前面的两个数来推后面的数，所以要从前向后遍历；
  • 打印dp数组(用来debug)：主要是看看我们写的代码的出来的dp数组是否是按我们想的那样。

    public int fib(int n) {
        if(n<2){
            return n;
        }
        int[] dp=new int[n+1];
        dp[0]=0;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }

• 思路：因为一次只能走1个或2个台阶，所以第n个台阶只能从第n-1或者n-2个台阶走上来(递推公式)。
  • 确定dp数组及下标含义：dp[ i ] 表示到 i+1 阶台阶有dp[ i ]种方法；
  • 确定递推公式：dp[ i ] = dp[ i-1 ]+dp[ i-2 ]；
  • dp数组的初始化：因为一次只能走1或2个台阶，所以走到1和2阶台阶的方法就是已知了，即dp[0]=1，dp[1]=2；
  • 确定遍历顺序：从递推公式可以看出，我们需要前面的两个数来推后面的数，所以要从前向后遍历。

  public int climbStairs(int n) {
      if(n<3){
          return n;
      }
      //dp[i]表示i+1阶台阶有几种爬楼方法
      int[] dp=new int[n];
      //递推公式——i>1(n>2)时,dp[i]=dp[i-1]+dp[i-2]
      //dp初始化——爬1阶台阶1种爬法，爬2阶台阶2种爬法
      dp[0]=1;
      dp[1]=2;
      for(int i=2;i<n;i++){
          dp[i]=dp[i-1]+dp[i-2];
      }
      return dp[n-1];
  }

• 思路：这道题首先要明确两点：
  （一）楼顶是哪？是cost的最后一个元素下标吗？
  ——楼顶是cost数组最后一个元素的下一个位置。
  （二）cost[ i ]代表站在第i个台阶的花费，还是从第i个台阶跳到下一个位置的花费？
  ——cost[ i ]代表从第i个台阶跳到下一个位置的花费。所以cost[ length-1 ]不是楼顶，是跳到楼顶的花费。
  • 确定dp数组及下标含义：dp[ i ] 表示到达第 i 个台阶的最小花费；
  • 确定递推公式：到达第 i 个台阶可以从第 i-1 或 i-2 个台阶过来， dp[i - 1] 跳到 dp[i] 需要花费 dp[i - 1] + cost[i - 1]，dp[i - 2] 跳到 dp[i] 需要花费 dp[i - 2] + cost[i - 2]，那么究竟是选从dp[i - 1]跳还是从dp[i - 2]跳呢？一定是选最小的，所以dp[ i ]=min(dp[ i-1 ]+cost[ i-1 ] , dp[ i-2 ]+cost[ i-2 ])；
    
  • dp数组的初始化：因为最开始可以选择站在第0或第1个台阶，同时站在该位置不花费体力，即dp[0]=0，dp[1]=0；
  • 确定遍历顺序：从递推公式可以看出，我们需要前面的两个数来推后面的数，所以要从前向后遍历。

    public int minCostClimbingStairs(int[] cost) {
        if(cost.length<2){
            return 0;
        }
        //dp[i]表示到达第i个台阶的最小花费，从0开始算，算上楼顶共有cost.length+1个台阶。
        int[] dp=new int[cost.length+1];
        //初始化dp
        dp[0]=0;
        dp[1]=0;
        for(int i=2;i<dp.length;i++){
            dp[i]=Math.min(dp[i-1]+cost[i-1],dp[i-2]+cost[i-2]);
        }
        return dp[dp.length-1];
    }

• 思路：
  • ★确定dp数组及下标含义：这道题确定dp的含义比较难想，一开始没想到。dp[i][j]代表从起点dp[0][0],走到dp[i][j]有几种不同的【走法】。
    【注意】有几种走法和需要走几步不同，求几种走法只需要加上前面的走法就行，而需要走几步，是按要求加上从上一个位置走过来需要的步数。(从递推公式就能看出来不同)
  • ★确定递推公式：一个不在最上或最左边的dp[i][j]，只能从dp[i][j]的上边或左边走过来，所以从起点走到dp[i][j]的走法应该等于上边+下边的走法。即dp[i][j]=dp[i-1][j]+dp[i][j-1]。
    
  • ★dp数组的初始化：根据递推公式可以发现，dp[i][j]需要从上边和左边得到，所以要对最上边和最左边进行初始化。因为只能向下和向右走，所以从起点走到最上边的任何一个位置都只有1种走法，同理从起点走到最左边的任何一个位置也都只有1种走法。
  • 确定遍历顺序：从递推公式可以看出，dp[i][j]需要从上边和左边得到，所以要从左到右、从上到下遍历。

  public int uniquePaths(int m, int n) {
      //★dp[i][j]代表从起点dp[0][0],走到dp[i][j]有几种不同的【走法】。
      int[][] dp=new int[m][n];
      //初始化
      dp[0][0]=1;
      for(int j=1;j<n;j++){
          dp[0][j]=1;
      }
      for(int i=1;i<m;i++){
          dp[i][0]=1;
      }
      for(int i=1;i<m;i++){
          for(int j=1;j<n;j++){
              dp[i][j]=dp[i-1][j]+dp[i][j-1];
          }
      }
      return dp[m-1][n-1];
  }

• 思路：这道题与上一道题唯一的区别就是可能遇到障碍。那么在初始化和递推公式时要注意：
  • 初始化时：对最上行和最左列初始化时，遇到障碍就停止初始化，因为障碍后面(下面)根本走不到了。
    
  • 递推公式：遇到障碍时，根本走不到(i，j)位置，所以 dp[i][j] 直接等于0就好；没遇到障碍时，还是dp[i][j]=dp[i-1][j]+dp[i][j-1]。

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        //行m列n
        int m=obstacleGrid.length;
        int n=obstacleGrid[0].length;
        //障碍在起点或终点，直接返回0
        if(obstacleGrid[0][0]==1||obstacleGrid[m-1][n-1]==1){
            return 0;
        }
        //dp[i][j]表示从起点走到(i,j)有几种走法
        int[][] dp=new int[m][n];//未初始化默认全0
        //初始化,遇到障碍就走不通了,直接停止初始化
        for(int i=0;i<m;i++){
            if(obstacleGrid[i][0]==1){
                break;
            }else{
                dp[i][0]=1;
            }
        }
        for(int j=0;j<n;j++){
            if(obstacleGrid[0][j]==1){
                break;
            }else{
                dp[0][j]=1;
            }
        }
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                //当前位置有障碍,说明根本走不到这里,则dp[i][j]就为0
                if(obstacleGrid[i][j]==1){
                    dp[i][j]=0;
                }else{
                    dp[i][j]=dp[i-1][j]+dp[i][j-1];
                }
            }
        }
        return dp[m-1][n-1];
    }

• 思路：对整数n(n>=2)进行拆分，可能会拆分成两个数相加、三个数相加、四个数相加...。这道题我们在拆分时，可以分成两种情况：两个数相加、三个或三个数以上相加。因为三个及三个以上相乘的时候，可以由两个数相乘来得到(递推公式的由来)。
  • 确定dp：这道题要求把n拆分后，若干个数的最大乘积，所以dp[ i ]代表把 i 拆分成若干个数后，这些书的最大乘积是dp[ i ]；
    
  • ★递推公式分两种情况：
    • 拆成两个数相加：i = j+(i-j)，则dp[i] = j * ( i - j )；
    • 拆成三个或三个数以上相加：i=j+m+n，则dp[i]=j*m*n；又因为移项后 i - j = m + n，所以dp[i] = j * dp[ i - j ]；
    同时，要求最大乘积，应该取上面两种情况的最大值，还要与之前的dp[i]进行比较，取最大值，即dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]))。
  • dp初始化：题目已经告诉我们n>=2，所以初始化时，让dp[2]=1开始即可。
  • ★遍历顺序：这道题在遍历时，需要两层for循环，一层对 i 遍历，表示递推的过程；一层对 j 遍历，表示把 i 进行拆分。

    public int integerBreak(int n) {
        //确定dp
        int[] dp=new int[n+1];//从0开始到n有n+1个数
        //初始化
        dp[2]=1;
        //因为是对dp[2]=1进行初始化，所以i从3开始即可
        for(int i=3;i<=n;i++){
            //★这里j最大只能到i-j，因为j+i-j=i，再大只是重复计算而已
            for(int j=1;j<=i-j;j++){
                //★取最大乘积
                dp[i]=Math.max(dp[i],Math.max(j*(i-j),j*dp[i-j]));
            }
        }
        return dp[n];
    }

• 思路：观察下面两幅图找规律。可以看出，n=3时，树的种类 = 以1为根的树的数量 + 以2为根的数量 + 以3为根的数量，而以1为根时，其右子树的两个节点的布局，和 n=2时候两棵树的布局是一样的；同理以2为根、以3为根左右子树的布局都遵循一样的规律。 
  
  
  • 确定dp：dp[i]代表有i个节点的二叉搜索树的种数；
  • ★递推公式：dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]，即dp[i] += dp[j-1] * dp[i-j]。
  • dp初始化：dp[0]=1; dp[1]=1;
  • 遍历顺序：两层for循环，第一层遍历节点数，第二层遍历根节点从1开始的情况。

    public int numTrees(int n) {
        //dp[i]代表有i个节点的二叉搜索树的种数
        int[] dp=new int[n+1];
        //0个节点即空树，也算1种，而不是0种，所以dp[0]=1而不是等于0。
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++){
            //分别遍历根节点从1到i的情况
            for(int j=1;j<=i;j++){
                //一共i个节点，对于根节点j时,左子树的节点个数为j-1，右子树的节点个数为i-j
                //★左子树*右子树(是*不是+!!!，★因为如果左右子树都只有1个节点，那么该树只有1*1种，而不是1+1=2种！！！)
                dp[i]+=dp[j-1]*dp[i-j];
            }
        }
        return dp[n];
    }

• 思路：将这道题抽象成背包问题，背包的最大容量应该是目标数组元素之和的一半。物品就是数组中的每个元素，物品重量和价值都是元素的数值大小。
             ★分割成两个等和子集的条件是什么呢？
             ——背包容量为原数组元素和一半时的最大价值 等于 原数组元素和的一半。即 dp[target]==target。
  • 确定dp：dp[ j ]代表容量为 j 的背包的最大价值；
  • ★递推公式：dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i])；
  • dp初始化：dp[0]=0；
  • 遍历顺序：先遍历物品，再倒序遍历容量

    public boolean canPartition(int[] nums) {
        int sumArr=0;
        //求原数组和
        for(int num:nums){
            sumArr+=num;
        }
        //元素和为奇数，则不能分成两个相等的子集
        if(sumArr%2!=0){
            return false;
        }
        //分割成两个等和子集后，一个子集的元素和
        int target=sumArr/2;
        //dp[j]表示容量为j的背包的最大价值
        //★背包最大容量=目标子集元素和
        int[] dp=new int[target+1];
        //初始化
        dp[0]=0;
        for(int i=0;i<nums.length;i++){
            for(int j=sumArr/2;j>=nums[i];j--){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        //★当背包容量为target时的最大价值dp[target]等于目标子集元素和target时，说明能分割成两个等和子集。
        return dp[target]==target;
    }

• 思路：这道题主要是解题思路难想，每次拿两块石头，要怎么往01背包上靠呢？其实可以从宏观来看，拿若干次，最终就会把一堆石头分成两堆，尽量使两堆的总重量相近，这样就能使最终石头的重量最小。这样就把问题转化成跟分割等和子集类似的问题了。物品重量和价值都是石头的重量。
  • 确定dp：dp[ j ]代表容量为 j 的背包能装的石头的最大重量；
  • ★递推公式：dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i])；
  • dp初始化：dp[0]=0。

    public int lastStoneWeightII(int[] stones) {
        int sum=0;
        for(int num:stones){
            sum+=num;
        }
        //将石头分成两堆，因为是向下取整，所以我们用背包装的这堆石头一定是小的那堆
        int bagWeight=sum/2;
        //物品的价值=石头的重量，物品的重量=石头重量
        //dp[j]表示容量为j的背包能装的最大石头重量(价值)
        int[] dp=new int[bagWeight+1];
        dp[0]=0;
        for(int i=0;i<stones.length;i++){
            for(int j=bagWeight;j>=stones[i];j--){
                dp[j]=Math.max(dp[j],dp[j-stones[i]]+stones[i]);
            }
        }
        //注意是两倍的背包重量
        return sum-2*dp[bagWeight];//等价于return (sum-dp[bagWeight])-dp[bagWeight]; //一堆减另一堆
    }

• 思路：这道题跟上一题差不多，通过给元素前添"+"或"-"号，也可以将原数组分为两堆，一堆全添"+"号，另一堆全添"-"号，让这两堆相碰，碰出target。所以这个问题就转化成了：
  将 nums 分为两组P和N，使得二者相减等于target。我们规定给P里的元素添"+"，给N里的元素添"-"号，例如： 假设nums = [1, 2, 3, 4, 5]，target = 3，一个可能的解决方案是+1-2+3-4+5 = 3 这里P = [1, 3, 5]和N = [2, 4]。根据题意可以得到以下两个关系式：
      ①P+N=sum(nums元素之和)
      ②P-N=target → N=P-target
  将②代入①可得，P=(sum+target)/2。所以我们可以理解为，从nums中任取元素，填满容量为P的背包有几种填法。
  
  • 确定dp：dp[ j ]代表填满容量为 j 的背包有dp[ j ]种填法；
  • ★递推公式：
    这道题递推公式比较重要。一维dp可由二维dp转化过来，所以我们可以曲线救国，通过二维dp得到一维dp的递推公式。
    dp[i][j]表示任取nums[0~i]填满容量为j的背包有dp[i][j]种填法。对于nums[i]可以选择取或者不取：
    - 不取nums[i]，要填满容量为j的背包，有dp[i-1][j]种填法，即dp[i][j] = dp[i-1][j]；
    - 取nums[i]，要填满容量为j的背包，有dp[i-1][j-nums[i]]种填法，即dp[i][j] = dp[i-1][j-nums[i]]；（注意这里只是求有几种填法）
    本题要求一共有几种填法，所以要把取和不取nums[i]的填法加起来，而不是取二者最大值，所以最终的递推公式应该是dp[i][j] = dp[i-1][j] + dp[i-1][j-nums[i]]。
    所以一维dp的递推公式，就是把二维dp的递推公式中的i去掉，即：dp[j]=dp[j]+dp[j-nums[i]]。
  • ★初始化：
    dp[0]代表填满容量为0的背包有几种填法，容量0都不取即可，所以算1种填法，即dp[0]=1。
  这道题还有两个无方案(直接return 0)的情况要特别注意：
  （一）如果给出的target比nums元素和还要大，那么一定没有合适的方案，比如[1,1,1,1]，target=5。同时target还可能是负数，所以target的绝对值大于sum的话，直接返回0。
  （二）如果(target+sum)是个奇数，即(target+sum)/2除不尽，这意味着不能把nums分成合适的两组，也可以直接返回0。

  public int findTargetSumWays(int[] nums, int target) {
      int sum=0;
      for(int n:nums){
          sum+=n;
      }
      int bagWeight=(target+sum)/2;
      //除不尽
      if((target+sum)%2==1){
          return 0;
      }
      //target太大了
      if(Math.abs(target)>sum){
          return 0;
      }
      //物品是原数组中的元素，weight是元素值，value是元素值。
      //dp[j]表示装满容量为j的背包有几种装法
      int[] dp=new int[bagWeight+1];
      //初始化
      dp[0]=1;//★放满容量为0的背包里有1中放法，即不取物品0！
      for(int i=0;i<nums.length;i++){
          for(int j=bagWeight;j>=nums[i];j--){
              dp[j]=dp[j]+dp[j-nums[i]];
          }
      }
      return dp[bagWeight];
  }

• 思路：本题中 strs 数组里的字符串就是物品，而 m 和 n 相当于是同一个背包，这个背包有两个维度，之前的背包都只有一个维度，只有一个重量的限制；而这道题的二维背包有两个限制——即0和1的个数限制。同理，每个物品(即字符串)也是二维的，有0的个数和1的个数。背包无论是一维还是二维整体思路都是一样的，只是在定义dp数组时有区别：
  
  • ★确定dp：dp[ i ][ j ]代表填满需要i个0和j个1的背包需要的最大物品个数；
    【tips】这里的dp还是滚动数组，相当于一维背包里的一维滚动dp，所以如果要定义成一维背包的二维dp的话，这里就应该定义为三维dp，多的一维是用来遍历物品的。
  • 递推公式：因为要求的是装满背包所需的最大物品个数，所以只存在取了该物品这一种状态(没取的话物品个数肯定不是最大的)，所以取了有n0个0，n1个1的物品后背包里的物品个数为 dp[i][j]=dp[i-n0][j-n1]+1，加的1就是放进去了一个物品。因为要求的最大物品数量，所以还要与之前的dp[i][j]比较取最大值，所以最终的递推公式为：dp[i][j]=Math.max(dp[i-n0][j-n1]+1 , dp[i][j]);
  • 遍历顺序：根据“先遍历物品，再倒序遍历容量”的规则，需要三层for循环，最外层遍历物品，剩下两层倒序遍历两个容量维度。

    public int findMaxForm(String[] strs, int m, int n) {
        //dp[i][j]代表装满需要i个0和j个1的背包需要的物品最大个数
        int[][] dp=new int[m+1][n+1];
        dp[0][0]=0;
        for(String s:strs){
            //统计字符串s中0和1的个数
            int n_0=0;
            int n_1=0;
            for(int k=0;k<s.length();k++){
                if(s.charAt(k)=='0'){
                    n_0++;
                }else{
                    n_1++;
                }
            }
            for(int i=m;i>=n_0;i--){
                for(int j=n;j>=n_1;j--){
                    //能放的最大物品个数，所以取max
                    dp[i][j]=Math.max(dp[i-n_0][j-n_1]+1,dp[i][j]);
                }
            }
        }
        return dp[m][n];
    }

• 思路：一看到钱币数量不限，首先想到这是一道完全背包问题。要注意本题是要求装满背包的物品组合种数。
  ★在求装满背包有几种方案的时候：
  ——如果求组合数，就要先遍历物品，再遍历容量。
  ——如果求排列数，就要先遍历容量，再遍历物品。
  

  public int change(int amount, int[] coins) {
      //dp[j]表示装满容量为j的背包有dp[j]种装法
      int[] dp=new int[amount+1];
      //全都不取，也算1种取法。
      dp[0]=1;
      for(int i=0;i<coins.length;i++){
          for(int j=coins[i];j<=amount;j++){
              dp[j]+=dp[j-coins[i]];
          }
      }
      return dp[amount];
  }

• 思路：这道题就是求装满背包有几种排列方案，所以在遍历时要先遍历背包再遍历物品。注意判断下标溢出的情况。

  public int combinationSum4(int[] nums, int target) {
      //dp[j]表示装满容量为j的背包有dp[j]种排列法。
      int[] dp=new int[target+1];
      dp[0]=1;
      //要求排列数，先背包后物品
      for(int j=0;j<=target;j++){//j从0开始，因为不知道要遍历哪个物品
          for(int i=0;i<nums.length;i++){
              //★j从0开始就要保证j-nums[i]>=0，防止下标溢出。
              if(j>=nums[i]){
                  dp[j]+=dp[j-nums[i]];
              }
          }
      }
      return dp[target];
  }

• 思路：注意这道题要求最小值，所以在对dp[j]进行初始化时，对非零下标不能再初始化为0(因为在递推公式中这个初始值0每次都是最小的，会覆盖正确的结果)，而应该初始化为Integer.MAX_VALUE。
             为什么要对dp[j-coins[i]]进行判断？
             ——★在取硬币时，要保证前面的取法能放进对应容量的背包，那么取当前硬币才有意义，如果前一个容量都满足不了，当前硬币就没有取的必要了，取了也满足不了。
  

  public int coinChange(int[] coins, int amount) {
      //dp[j]表示填满容量为j的背包所需的最少物品个数为dp[j]
      int[] dp=new int[amount+1];
      dp[0]=0;
      //★因为要求最小值，所以要将非零容量初始化为MAX_VALUE，不能初始化为其他值，防止二者取小时覆盖结果
      for(int j=1;j<=amount;j++){
          dp[j]=Integer.MAX_VALUE;
      }
      for(int i=0;i<coins.length;i++){
          for(int j=coins[i];j<=amount;j++){
              //★★如果dp[j-coins[i]]是无穷大，说明无法凑出j-coins[i]价值的钱包，那么把coins[i]放进去以后，自然也凑不出dp[j]的钱包，所以只有前一个能放，后一个才有放的必要
              if(dp[j-coins[i]]!=Integer.MAX_VALUE){
                  dp[j]=Math.min(dp[j],dp[j-coins[i]]+1);
              }
          }
      }
      //★如果dp[amount]还是初始值Integer.MAX_VALUE，说明用所给硬币面额凑不出总金额。
      return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
  }

• 思路：这道题跟上一道题差不多，注意一下遍历完全平方数的方法即可。

  public int numSquares(int n) {
      //dp[j]表示装满容量为j的背包最少需要dp[j]个物品(完全平方数)。
      int[] dp=new int[n+1];
      dp[0]=0;
      for(int j=1;j<=n;j++){
          dp[j]=Integer.MAX_VALUE;
      }
      //★完全平方数1,4,9,16分别是1,2,3,4的平方，所以遍历所有的完全平方数不用挨个判断i是不是完全平方数，用i*i就能得到每一个完全平方数
      for(int i=1;i*i<=n;i++){
          for(int j=i*i;j<=n;j++){
              dp[j]=Math.min(dp[j],dp[j-i*i]+1);
          }
      }
      return dp[n];
  }

• 思路：这道题给定的字符串s相当于背包，字典中的单词相当于物品，且单词可重复使用，那么就可以转化成完全背包问题。
  
  • ★确定dp：boolean dp[j]表示能否(true/false)用字典中的单词（物品）填满s中长度为j的子串(相当于容量为j的背包)；
    
  • ★递推公式：比如说取了长度为len的单词wordDict.get(i)，那么能否用该单词填满长度为j的子串，取决于：
    ①前面长度为j-len的子串是否已经被填满了，即 dp[j-len]==true；
    ②该单词wordDict.get(i)能否与子串要填的部分(str)匹配上，即 str.equals(wordDict.get(i))；
    所以，递推公式是

    if(dp[j-len]&&str.equals(wordDict.get(i))){
        dp[j]=true;
    }

  • 初始化：
    -- dp[0]：根据递推公式，dp[0]必须初始化为true，如果dp[0]=false，递推公式的if判断会一直是false，那么推出的其他dp[j]全都是false了。
    -- 其他非零下标dp：初始化为false。
  • ★★遍历顺序：这道题只能先遍历字符串(背包)，再遍历字典中的单词(物品)。前面我们说求组合数要先物品后背包，求排列数要先背包后物品。这道题拿 s = "applepenapple", wordDict = ["apple", "pen"] 举例。"apple", "pen" 是物品，那么我们要求的物品的组合一定是 "apple" + "pen" + "apple" 才能组成 "applepenapple"。"apple" + "apple" + "pen" 或者 "pen" + "apple" + "apple" 是不可以的，所以本题是要强调物品顺序的，因此求的是排列数，所以要先背包后物品。
    

    public boolean wordBreak(String s, List<String> wordDict) {
        //★dp[j]表示能否用字典中的单词填满s中长度为j的子串
        boolean[] dp=new boolean[s.length()+1];
            //初始化
        Arrays.fill(dp,false);
        dp[0]=true;
        //★求排列——先背包后物品
        for(int j=0;j<=s.length();j++){
            for(int i=0;i<wordDict.size();i++){
                int len=wordDict.get(i).length();
                //字典中的单词比子串长，一定不能填满子串
                if(len>j){
                    continue;
                }
                //截取子串
                String str=s.substring(j-len,j);
                //★如果前面都可以填满且这次要填的单词与缺的子串相等，则dp[j]=true。
                if(dp[j-len]&&str.equals(wordDict.get(i))){
                    dp[j]=true;
                }
            }
        }
        return dp[s.length()];
    }

• 思路：偷的规则是偷完上一家就不能偷下一家。对于当前房间只有两种状态——偷与不偷，而且偷与不偷的金钱数还与前两个房间的状态有关（递推公式）。
  • 确定dp：dp[i]表示经过第 i 个房间(从0开始)后的获得的最高金额为dp[i]；
    
  • ★递推公式：
    -- 偷当前房间 i，那么手里的最高金额是经过前 i-2 个房间后的最高金额(dp[i-2])加上当前房间的金额，即dp[i]=dp[i-2]+nums[i]；
    -- 不偷当前房间 i，那么手里的最高金额是经过前 i-1 个房间后的最高金额(dp[i-1])，即dp[i]=dp[i-1]。
    二者取最大，即dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1])。
  • 初始化：由递推公式可知，dp[i]与前两个房间有关，所以需要对dp[0]和dp[1]进行初始化。

    public int rob(int[] nums) {
        if(nums.length==1){
            return nums[0];
        }
        //dp[i]表示经过第i个房屋(从0开始)的最高金额
        int[] dp=new int[nums.length];
        //初始化
        dp[0]=nums[0];
        dp[1]=Math.max(nums[0],nums[1]);
        for(int i=2;i<nums.length;i++){
            dp[i]=Math.max(dp[i-2]+nums[i],dp[i-1]);
        }
        return dp[nums.length-1];
    }

• 思路：本题与上一题唯一不同是房间连成环了，这意味着偷第一家就不能偷最后一家，偷最后一家就不能偷第一家，该如何解决房间成环的问题呢？
  ——我们可以在上一题的基础上，分为两种情况考虑：
  ①偷第一家，不偷最后一家：此时相当于没有最后一家，就把环变成线性的了。
      
  ②偷最后一家，不偷第一家：此时相当于没有第一家。
      
  将问题分成以上两种情况，每种情况都可以用上一题的方法来解决，分别得到两种情况的最大金额，二者再取最大值，即为所求。
  

  public int rob(int[] nums) {
      if(nums.length==1){
          return nums[0];
      }
      if(nums.length==2){
          return Math.max(nums[0],nums[1]);
      }
      //情况1：顾头不顾尾
      int[] dp1=new int[nums.length-1];
      dp1[0]=nums[0];
      dp1[1]=Math.max(nums[0],nums[1]);
      for(int i=2;i<nums.length-1;i++){
          dp1[i]=Math.max(dp1[i-2]+nums[i],dp1[i-1]);
      }
      //情况2：顾尾不顾头
      int[] dp2=new int[nums.length-1];
      dp2[0]=nums[1];
      dp2[1]=Math.max(nums[1],nums[2]);
      for(int i=2;i<nums.length-1;i++){
          dp2[i]=Math.max(dp2[i-2]+nums[i+1],dp2[i-1]);
      }
      return Math.max(dp1[dp1.length-1],dp2[dp2.length-1]);
  }

• 思路：二叉树dp。这道题与上两道题一样，还是要考虑当前房间偷与不偷的问题，只不过前两题是线性数组，用for循环遍历；而这道题是二叉树，用递归代替for循环遍历。
  • ★返回值类型：要求两种状态(偷与不偷)下的最大金额，所以返回值要是一个长度为2的数组。
                            相应的dp数组也要定义成长度为2的数组，dp[0]表示不偷当前节点的最大金额,dp[1]表示偷当前节点的最大金额；
  • 终止条件：偷和不偷空节点的最大金额都是0，所以遇到空节点返回{0,0}；
    
  • ★递归逻辑(递推公式)：采用后序遍历，先获取左右孩子两种状态下的最大金额，再对当前节点进行分析：
    ①不偷当前节点的最大金额dp[0]：不偷当前节点的最大金额，应该由左右孩子决定，即偷与不偷左右孩子的最大金额之和，即dp[0]=Math.max(leftDp[0],leftDp[1])+Math.max(rightDp[0],rightDp[1])；
    ②偷当前节点的最大金额dp[1]：偷了当前节点一定没偷左右孩子，所以偷当前节点的最大金额应该等于当前节点的金额加上左右节点不偷状态下的最大金额，即dp[1]=root.val+leftDp[0]+rightDp[0]；

  class Solution {
      public int rob(TreeNode root) {
          int[] rslt=robAction(root);
                  //★返回偷与不偷两种状态的最大金额
          return Math.max(rslt[0],rslt[1]);
      }
      public int[] robAction(TreeNode root){
          //dp[0]表示不偷当前节点的最大金额,dp[1]表示偷当前节点的最大金额
          int[] dp=new int[2];
          //终止条件
          if(root==null){
              //偷和不偷空节点的最大金额都是0
              return dp;
          }
          //后序遍历
          int[] leftDp=robAction(root.left);
          int[] rightDp=robAction(root.right);
          //★不偷当前节点
          dp[0]=Math.max(leftDp[0],leftDp[1])+Math.max(rightDp[0],rightDp[1]);
          //偷当前节点
          dp[1]=root.val+leftDp[0]+rightDp[0];
          return dp;
      }
  }

• 思路一：贪心。因为只有一只股票且就买卖一次，那么贪心的想法就是取最左最小值，取最右最大值，那么得到的差值就是最大利润。

  class Solution {
      public int maxProfit(int[] prices) {
          int min=Integer.MAX_VALUE;
          int rslt=0;
          for(int i=0;i<prices.length;i++){
              min=Math.min(prices[i],min);// 取最左最小价格
              rslt=Math.max(rslt,prices[i]-min);// ★直接取最大区间利润
          }
          return rslt;
      }
  }

• ★思路二：dp。
  • ★确定dp数组的含义：定义成二维dp数组。
    -- dp[i][0]表示第i天 不持有 股票能获取的最大利润；
    -- dp[i][1]表示第i天 持有 股票能获取的最大利润。
    为什么一维dp不行呢？
    ——因为每天的状态有持有和不持有股票两种，而一维dp的下标只能表示第几天，所以需要第二维再表示当前的状态。
    ★为什么不表示买入和卖出股票而要表示持有和不持有股票？
    ——因为本题只有一只股票且只能买卖一次，如果单纯的表示当天买入或卖出股票，比如第三天买入，那么第一天第二天是不持有股票的，就没法表示第一第二天的状态了。所以要表示持有和不持有股票。
  • ★递推公式：
    第i天有两种状态：
        1）如果第i天不持有股票，此时最大利润可以由两个状态推出：
            ①i-1天也不持有股票，那么第i天不持有股票的最大利润等于前一天不持有股票的最大利润，即dp[i][0]=dp[i-1][0]；
            ②i-1天持有股票，但是第i天把股票卖了导致的不持有股票，那么第i天不持有股票的最大利润等于第i-1天持有股票的最大利润+卖出股票的价格，即dp[i][0]=dp[i-1][1]+prices[i]；
        二者取最值，即dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i])。
        2）如果第i天持有股票，此时最大利润可以由两个状态推出：
            ①i-1天也持有股票，那么第i天持有股票的最大利润等于前一天持有股票的最大利润，即dp[i][1]=dp[i-1][1]；
            ②i-1天不持有股票，是第i-1天第一次买入了股票导致的持有股票，那么第i天持有股票的最大利润等于买入股票的价格，即dp[i][1]=-prices[i]；
        二者取最值，即dp[i][1]=Math.max(dp[i-1][1],-prices[i])。
  • 初始化：从递归公式可以看出，第i天的两个状态分别与第i-1的两个状态有关，所以对第0天的两个状态初始化：
        dp[0][0]=0；
        dp[0][1]= - prices[0]。
    

  public int maxProfit(int[] prices) {
      //dp[i][0]表示第i天 不持有 股票能获取的最大利润
      //dp[i][1]表示第i天 持有 股票能获取的最大利润
      int[][] dp=new int[prices.length][2];
      dp[0][0]=0;
      dp[0][1]=-prices[0];
      for(int i=1;i<prices.length;i++){
          dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
          dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
      }
      return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);
  }

• 思路一：贪心。

  public int maxProfit(int[] prices) {
      int sum=0;
      for(int i=0;i<prices.length-1;i++){
          int cha=prices[i+1]-prices[i];
          if(cha>0){
              sum+=cha;
          }
      }
      return sum;
  }

• 思路二：dp。这道题与上一题121唯一不同就是可以买卖多次，所以在当天持有股票的递推公式中，如果是当天买入股票(-prices[i])，还需要加上把之前股票卖掉的利润(不持有股票的最大利润)。

  public int maxProfit(int[] prices) {
          //dp[i][0]表示第i天 不持有 股票能获取的最大利润 
          //dp[i][1]表示第i天 持有 股票能获取的最大利润
      int[][] dp=new int[prices.length][2];
      dp[0][0]=0;
      dp[0][1]=-prices[0];
      for(int i=1;i<prices.length;i++){
          dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
          dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);// 注意这里是和121题唯一不同的地方。
      }
      return Math.max(dp[prices.length-1][0],dp[prices.length-1][1]);
  }

（3）★123. 买卖股票的最佳时机 III

• 思路：买卖股票的问题难点和突破口就是找准每天可能的状态。这道题可以不买卖、可以买卖一次、可以买卖两次，所以每天的状态就有4种，最终结果就是4种状态中的最大值。
  • ★确定dp数组：第i天有4种状态：
    • dp[i][0]表示第i天 第一次不持有 股票能获取的最大利润
    • dp[i][1]表示第i天 第一次持有 股票能获取的最大利润
    • dp[i][2]表示第i天 第二次不持有 股票能获取的最大利润
    • dp[i][3]表示第i天 第二次持有 股票能获取的最大利润
  • 递推公式：
    • 第i天第一次不持有股票的最大利润dp[i][0]与两个状态有关：
      • 前一天也不持有股票：dp[i][0]=dp[i-1][0]；
      • 前一天持有但第i天卖出：dp[i][0]=dp[i-1][1]+prices[i][0]；
    • 第i天第一次持有股票的最大利润dp[i][1]与两个状态有关：
      • 前一天也持有股票：dp[i][1]=dp[i-1][1]；
      • 前一天不持有但第i天买入(第一次买入)：dp[i][1]=-prices[i]；
    • 第i天第二次不持有股票的最大利润dp[i][2]：
      • 前一天也不持有股票：dp[i][2]=dp[i-1][2]；
        
      • 前一天持有(第二次持有)但第i天卖出：dp[i][2]=dp[i-1][3]+prices[i]；
    • 第i天第二次持有股票的最大利润dp[i][3]：
      • 前一天也持有股票：dp[i][3]=dp[i-1][3]；
      • 前一天不持有(第一次不持有)但第i天买入：dp[i][3]=dp[i-1][0]-prices[i]；
  • 初始化：分别对第0天的四种状态初始化：
    • dp[0][0]=0；
    • dp[0][1]=-prices[0]；
    • dp[0][2]=0；
    • dp[0][3]=-prices[0]

  public int maxProfit(int[] prices) {
      //dp[i][0]表示第i天 第一次不持有 股票能获取的最大利润 
      //dp[i][1]表示第i天 第一次持有 股票能获取的最大利润
      //dp[i][2]表示第i天 第二次不持有 股票能获取的最大利润
      //dp[i][3]表示第i天 第二次持有 股票能获取的最大利润
      int[][] dp=new int[prices.length][4];
      dp[0][0]=0;
      dp[0][1]=-prices[0];
      dp[0][2]=0;
      dp[0][3]=-prices[0];
      for(int i=1;i<prices.length;i++){
          dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]);
          dp[i][1]=Math.max(dp[i-1][1],-prices[i]);
          dp[i][2]=Math.max(dp[i-1][2],dp[i-1][3]+prices[i]);
          dp[i][3]=Math.max(dp[i-1][3],dp[i-1][0]-prices[i]);
      }
      return Math.max(Math.max(dp[prices.length-1][0],dp[prices.length-1][1]),Math.max(dp[prices.length-1][2],dp[prices.length-1][3]));
  }

• 思路：多增加一个维度表示买卖次数，这样每天的状态还是两种——持有/不持有。
  • ★确定三维dp数组：[第几天][买卖次数][0-不持有/1-持有]
  • 递推公式：每天的状态只有不持有-0和持有-1两种，注意是否用到上一次买卖的股票！：
    1）第i天第j次买卖，不持有股票：
        ①前一天也不持有股票：dp[i-1][j][0]；
        ②前一天持有股票但第i天卖了：dp[i-1][j][1]+prices[i]；
    2）第i天第j次买卖，持有股票：
        ①前一天也持有股票：dp[i-1][j][1]；
        ②前一天不持有股票但第i天买入了，注意前一天是第j-1次买卖，第i天买入的是新一次买卖即第j次买卖了：dp[i-1][j-1][0]-prices[i]；
  • 初始化：对第一天所有交易次数进行初始化：

    for (int i = 0; i <= k; i++) {
        // dp[0][i][0]初始化为0，这里不用再初始化了，因为创建dp时默认就是0了
        dp[0][i][1] = -prices[0];
    }

  public int maxProfit(int k, int[] prices) {
      if(k==0||prices.length==0) return 0;
      //[第几天][买卖次数][0-不持有/1-持有]
      int[][][] dp=new int[prices.length][k+1][2];
      //★初始化所有交易次数
      for (int i = 0; i <= k; i++) {
                  // dp[0][i][0]初始化为0，这里不用再初始化了，因为创建dp时默认就是0了
          dp[0][i][1] = -prices[0];
      }
      for(int i=1;i<prices.length;i++){
          for(int j=1;j<=k;j++){
              dp[i][j][0]=Math.max(dp[i-1][j][0],dp[i-1][j][1]+prices[i]);
              dp[i][j][1]=Math.max(dp[i-1][j][1],dp[i-1][j-1][0]-prices[i]);
          }
      }
      return Math.max(dp[prices.length-1][k][0],dp[prices.length-1][k][1]);
  }

• 思路：一只股票，可多次买卖。但卖出后隔一天才能再买入。第i天的状态有4种：0-持有股票；1-冷冻期后保持卖出状态没买入；2-卖出股票；3-冷冻期。其中状态1和状态2合起来是不持有股票的状态(冷冻期单独算)。

  class Solution {
      public int maxProfit(int[] prices) {
          //第i天的状态有4种：0-持有股票；1-冷冻期后保持卖出状态没买入；2-卖出股票；3-冷冻期
          int[][] dp=new int[prices.length][4];
          //第0天买入股票
          dp[0][0]=-prices[0];
          dp[0][1]=0;
          dp[0][2]=0;
          dp[0][3]=0;
          for(int i=1;i<prices.length;i++){
              dp[i][0]=Math.max(Math.max(dp[i-1][0],dp[i-1][1]-prices[i]),dp[i-1][3]-prices[i]);
              dp[i][1]=Math.max(dp[i-1][1],dp[i-1][3]);
              dp[i][2]=dp[i-1][0]+prices[i];
              dp[i][3]=dp[i-1][2];
          }
          return Math.max(Math.max(dp[prices.length-1][0],dp[prices.length-1][1]),Math.max(dp[prices.length-1][2],dp[prices.length-1][3]));
      }
  }

• 思路：一只股票，可多次买卖，每次买卖需交一次手续费。这道题与122.买卖股票的最佳时机II 唯一不同就是只要买卖一次需要支付一次手续费，所以在递推公式处有区别。

  public int maxProfit(int[] prices, int fee) {
      int len=prices.length;
      //第i天有两个状态：0-不持有股票；1-持有股票
      int[][] dp=new int[len][2];
      //★卖出时支付手续费
      dp[0][0]=0;
      dp[0][1]=-prices[0];
      for(int i=1;i<len;i++){
          //★与122.买卖股票的最佳时机II唯一区别的地方，要扣减手续费
          dp[i][0]=Math.max(dp[i-1][0],dp[i-1][1]+prices[i]-fee);
          dp[i][1]=Math.max(dp[i-1][1],dp[i-1][0]-prices[i]);
      }
      return Math.max(dp[len-1][0],dp[len-1][1]);
  }

• 思路：注意初始化和递推公式。

  public int lengthOfLIS(int[] nums) {
      //以nums[i]为结尾的严格递增子序列的最大长度
      int[] dp=new int[nums.length];
      //★每个元素自己也是一个长度为1的严格递增子序列，所以dp[i]至少是1
      Arrays.fill(dp,1);
      for(int i=1;i<nums.length;i++){
          //从第0个元素开始，依次作为子序列的起始位置
          for(int j=0;j<i;j++){
              //★如果nums[j]<nums[i]，dp[i]就等于dp[j]+1，加的1是nums[j]
              if(nums[j]<nums[i]){
                  dp[i]=Math.max(dp[i],dp[j]+1);
              }
              //如果nums[j]>=nums[i]，就跳过，不用更新dp[i]  
          }
      }
      //遍历dp数组，找出最大值
      int rslt=0;
      for(int len:dp){
          rslt=rslt>len?rslt:len;
      }
      return rslt;
  }

• 思路：本题与上一题的区别就是，上一题是子序列，可以不连续；本题要求连续子序列，所以就只比较nums[i]与nums[i - 1]，不用去比较nums[j]与nums[i] （j是在0到i之间遍历）。

  public int findLengthOfLCIS(int[] nums) {
      //dp[i]表示以nums[i]结尾的连续严格递增子序列的最大长度
      int[] dp=new int[nums.length];
      Arrays.fill(dp,1);
      int rslt=1;
      for(int i=1;i<nums.length;i++){
          //因为是连续的，所以dp[i]只与前一个位置有关
          if(nums[i-1]<nums[i]){
              dp[i]=Math.max(dp[i],dp[i-1]+1);
          }
          //更新结果长度
          rslt=rslt>dp[i]?rslt:dp[i];
      }
      return rslt;
  }

• 思路：这道题难在如何定义dp数组。因为涉及到两个数组，所以我们考虑用二维dp数组来表示两个数组的状态。
  为什么 dp[i][j] 表示 i-1 和 j-1 而不是 i 和 j ？
  ——这样定义是为了在初始化和写递推公式时方便。如果dp[i][j]代表i和j的话，dp[0][0]就要由dp[-1][-1]来求得，这显然是不合理的，在初始化时就要对dp[0][j]和dp[i][0]单独进行初始化，并且在写递推公式时要判断i、j不为负数。
  
  

  public int findLength(int[] nums1, int[] nums2) {
      //★dp[i][j]表示以nums1[i-1]为结尾的子数组和以nums2[j-1]为结尾的子数组的公共子数组的最大长度。
      int[][] dp=new int[nums1.length+1][nums2.length+1];
      //初始化——全是0
      //最大长度
      int rslt=0;
      //★根据dp定义，dp[0][j]和dp[i][0]都是无意义的，所以要从dp[1][1]开始
      for(int i=1;i<nums1.length+1;i++){
          for(int j=1;j<nums2.length+1;j++){
              //★递推公式：两数相等，就要在dp[i-1][j-1]的基础上加1。
              if(nums1[i-1]==nums2[j-1]){
                  dp[i][j]=dp[i-1][j-1]+1;
              }
              rslt=Math.max(rslt,dp[i][j]);
          }
      }
      return rslt;
  }

• 思路：这道题与上一道题类似，只不过上一道题求最长重复数组，求的是连续的；这道题求最长公共子序列，可以不连续。因此在递推公式上，有所不同。

  public int longestCommonSubsequence(String text1, String text2) {
      char[] arr1=text1.toCharArray();
      char[] arr2=text2.toCharArray();
      //dp[i][j]表示以arr1[i-1]为结尾的子序列和以arr2[j-1]为结尾的子序列的公共子序列的最大长度
      int[][] dp=new int[text1.length()+1][text2.length()+1];
      //都初始化为0
      //遍历
      for(int i=1;i<text1.length()+1;i++){
          for(int j=1;j<text2.length()+1;j++){
              if(arr1[i-1]==arr2[j-1]){
                  dp[i][j]=dp[i-1][j-1]+1;
              }else{
                  //与718. 最长重复子数组的区别
                  //★如果arr1[i-1](c)和arr2[j-1](e)不相等，比如"abc"和"ace"的c和e不等了，就要从"abc"和"ac"的公共子序列的最大长度 与 "ab"和"ace"的公共子序列的最大长度中取最大值
                  dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
              }
          }
      }
      //返回text1和text2的公共子序列的最大长度
      return dp[text1.length()][text2.length()];
  }

• 思路：这道题就是要求nums1和nums2的最长公共子序列的长度，跟上一题是一样的。

  public int maxUncrossedLines(int[] nums1, int[] nums2) {
      //dp[i][j]表示以nums1[i]为结尾和以nums[j]为结尾的子数组的公共子序列的最大长度
      int[][] dp=new int[nums1.length+1][nums2.length+1];
      for(int i=1;i<=nums1.length;i++){
          for(int j=1;j<=nums2.length;j++){
              if(nums1[i-1]==nums2[j-1]){
                  dp[i][j]=dp[i-1][j-1]+1;
              }else{
                  dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
              }
          }
      }
      return dp[nums1.length][nums2.length];
  }

• 思路一：贪心。
• 思路二：dp。这道题想清楚递推公式即可。
  dp[i]只有两个方向可以推出来：
  • dp[i - 1] + nums[i]，即：nums[i]加入当前连续子序列和
  • nums[i]，即：从头开始计算当前连续子序列和

  一定是取最大的，所以dp[i] = max(dp[i - 1] + nums[i], nums[i]);

  public int maxSubArray(int[] nums) {
      //dp[i]表示以nums[i]为结尾的连续子数组的最大和
      int[] dp=new int[nums.length];
      //初始化
      for(int i=0;i<dp.length;i++){
          dp[i]=nums[i];
      }
      int rslt=dp[0];
      for(int i=1;i<dp.length;i++){
          //递推公式
          dp[i]=Math.max(dp[i-1]+nums[i],dp[i]);
          rslt=Math.max(rslt,dp[i]);
      }
      return rslt;
  }

• 思路一：双指针（推荐）。如果s是t的子序列，也就是说s中的所有字符都会按照顺序出现在t中。

  public boolean isSubsequence(String s, String t) {
      //双指针
      int sp=0;
      int tp=0;
      while(sp<s.length()&&tp<t.length()){
          if(s.charAt(sp)==t.charAt(tp)){
              sp++;
          }
          tp++;
      }
      //如果s是t的子序列，sp会走到s的末尾
      if(sp==s.length()){
          return true;
      }else{//如果s不是t的子序列，在上面sp就不会加1了，那么sp就不会走到s的末尾
          return false;
      }
  }

• 思路二：dp。

  public boolean isSubsequence(String s, String t) {
      //dp[i][j]表示以s(i-1)和t(j-1)为结尾的字符串的公共子串的长度
      int[][] dp=new int[s.length()+1][t.length()+1];
      //将dp[0][0]和dp[i][0]初始化为0
      //遍历
      for(int i=1;i<dp.length;i++){
          for(int j=1;j<dp[0].length;j++){
              if(s.charAt(i-1)==t.charAt(j-1)){
                  dp[i][j]=dp[i-1][j-1]+1;
              }else{
                  dp[i][j]=dp[i][j-1];
              }
          }
      }
      //dp[i][j]表示以下标i-1为结尾的字符串s和以下标j-1为结尾的字符串t相同子序列的长度，所以如果dp[s.size()][t.size()] 与 字符串s的长度相同说明：s与t的最长相同子序列就是s，那么s 就是 t 的子序列。
      if(dp[s.length()][t.length()]==s.length()){
          return true;
      }else{
          return false;
      }
  }

• 思路：注意这道题只是说“子序列”，也就是说可以不连续，如果说“连续子序列”，这道题就是kmp了。这道题问 s 的子序列中有多少个和 t 一样的，就可以转化成 s 中有几种删除元素的方式，能让 s 变成 t 。
  • 定义dp数组：像两个字符串比较相同元素这种dp，一般要定义成二维dp，才能把这两个字符串里面每个元素的比较情况都展现出来。dp[i][j] 表示以 i-1 为结尾的 s 中包含的以 j-1 为结尾的 t 的个数为dp[i][j]；
  • ★确定递推公式：我们要确定dp[i][j]怎么得来的：
            如果s[i-1]和t[j-1]的字符相等的时候，而且对于s[i-1]这个元素，可能用(s=bag，t=bag)，也可能不用(s=bagg，t=bag，这种情况下不用第二个g，也能满足s中有t)，所以此时dp[i][j]=dp[i-1][j-1] + dp[i-1][j]；
            如果二者不相等，一定不用s[i-1]，所以此时dp[i][j]=dp[i-1][j]。
    综上，递推公式是：
            
    
  • ★初始化：从递推公式中可以看出，需要对二维dp的第一行和第一列进行初始化：
            第一行即dp[0][j]，表示s为空字符串时，包含几个t，显然是0个；
            第一列即dp[i][0]，表示s中包含几个空字符串t，显然s只有1个空子序列，所以是1个；
            第一行第一列的交集即dp[0][0]，表示空串s中包含几个空串t，显然是1个。

    public int numDistinct(String s, String t) {
        //dp[i][j] 表示以 i-1 为结尾的 s 中包含的以 j-1 为结尾的 t 的个数为dp[i][j]
        int[][] dp=new int[s.length()+1][t.length()+1];
        //★初始化——从递推公式中可以看出，需要对二维dp的第一行和第一列进行初始化
        //第一行即dp[0][j]，表示s为空字符串时，包含几个非空t，显然是0个
        //第一列即dp[i][0]，表示s中包含几个空字符串t，显然s只有1个空子序列，所以是1个
        //第一行第一列的交集即dp[0][0]，表示空串s中包含几个空串t，显然是1个
        for(int i=0;i<dp.length;i++){
            dp[i][0]=1;
        }
        //第一行为0，默认初始值就是0，这里就不进行初始化了
        //遍历
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp[0].length;j++){
                if(s.charAt(i-1)==t.charAt(j-1)){
                    //s[i-1]==t[j-1]的时候，可以用到s[i-1]，也可能不用s[i-1]
                    dp[i][j]=dp[i-1][j-1]+dp[i-1][j];
                }else{
                    //s[i-1]!=t[j-1]的时候，一定是不用s[i-1]的情况
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[s.length()][t.length()];
    }

• 思路一：这道题相较于上面那道题的区别就是，两个字符串都要进行删除操作。
  • 定义二维dp数组：dp[i][j]表示让以 i-1 为结尾的word1和以 j-1 为结尾的word2相同所需要删除的最少次数为dp[i][j]。
  • ★递推公式：
    • 如果word1[i-1] == word2[j-1]，那么就不需要删除这两个元素，dp[i][j]跟dp[i-1][j-1]就是一样的，即dp[i][j] = dp[i-1][j-1]；
      
    • 如果word1[i-1] != word2[j-1]，可能删除word[i-1]，也可能删除word2[j-1]，也可能两个都删，而且要加上删除次数，同时取最小的那个，即dp[i][j] = Math.min(dp[i-1][j]+1，dp[i][j-1]+1，dp[i-1][j-1]+2)。
  • 初始化：同样由递推公式可以看出，第一行和第一列都要初始化：
        第一行即dp[0][j]，也就是说word1为空，那么最少删除次数就是word2的长度，即j；
        第一列即dp[i][0]，同理word2为空，最少删除次数就是word1的长度，即i；
        dp[0][0]，两个都是空，最少删除次数是0。

    public int minDistance(String s1, String s2) {
        int[][] dp=new int[s1.length()+1][s2.length()+1];
        for(int i=1;i<dp.length;i++){
            dp[i][0]=i;
        }
        for(int j=1;j<dp[0].length;j++){
            dp[0][j]=j;
        }
        for(int i=1;i<dp.length;i++){
            for(int j=1;j<dp[0].length;j++){
                if(s1.charAt(i-1)==s2.charAt(j-1)){
                    dp[i][j]=dp[i-1][j-1];
                }else{
                    dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+2);
                }
            }
        }
        return dp[s1.length()][s2.length()];
    }

• 思路二：这道题也可以用“公共最长子序列”来做，删除后word1和word2剩的相同部分，其实就是二者的最长公共子序列，那么最少删除次数 = word1.length() + word2.length() - 2×公共最长子序列.length()。

• 思路：编辑距离问题涉及到删除、替换、插入字符，所以要比前面做的只删除元素难一点。
• 定义dp数组：dp[i][j]表示让以 i-1 为结尾的word1和以 j-1 为结尾的word2相同所需要的最少操作次数为dp[i][j]。
• ★确定递推公式：
  • 如果word1[i-1] == word2[j-1]，那么就不需要操作这两个元素，dp[i][j]跟dp[i-1][j-1]就是一样的，即dp[i][j] = dp[i-1][j-1]；
    
  • ★如果word1[i-1] != word2[j-1]，需要进行增删替的操作，这里注意，增和删是两个互逆的操作，对word1增相当于对word2删，所以这里只考虑删除操作即可。
        删除的话跟上一题一样，既可以删word1[i-1]，也可以删word2[j-1]，同时要加一次操作；
        ★替换的话，举个例子比如word1="ab"，word2="ac"，我们需要将b替换成c，很明显在以a结尾的两个word的基础上做的一次操作，所以dp[i][j]=dp[i-1][j-1]+1。
    综上，dp[i][j] = Math.min(dp[i-1][j]+1，dp[i][j-1]+1，dp[i-1][j-1]+1)。
• 初始化：初始化跟上面道题一样的：
      第一行即dp[0][j]，也就是说word1为空，那么最少删除次数就是word2的长度，即j；
      第一列即dp[i][0]，同理word2为空，最少删除次数就是word1的长度，即i；
      dp[0][0]，两个都是空，最少删除次数是0。

  public int minDistance(String s1, String s2) {
      int[][] dp=new int[s1.length()+1][s2.length()+1];
      for(int i=1;i<dp.length;i++){
          dp[i][0]=i;
      }
      for(int j=1;j<dp[0].length;j++){
          dp[0][j]=j;
      }
      for(int i=1;i<dp.length;i++){
          for(int j=1;j<dp[0].length;j++){
              if(s1.charAt(i-1)==s2.charAt(j-1)){
                  dp[i][j]=dp[i-1][j-1];
              }else{
                  dp[i][j]=Math.min(Math.min(dp[i-1][j]+1,dp[i][j-1]+1),dp[i-1][j-1]+1);
              }
          }
      }
      return dp[s1.length()][s2.length()];
  }

• 思路一：这道题的暴力解法，就是两层for循环分别来确定字符串的起始和结束位置，也就是确定一个范围，再通过一个for循环来判断是不是回文串。这样的时间复杂度是O(n3)。
• 思路二：dp。
  • ★确定dp的含义：定义一个二维boolean dp，dp[i][j]表示以s[i]为起始、以s[j]为结尾的子串是否是回文子串。
  • ★确定递推公式：
    • 如果s[i]==s[j]，要考虑三种情况：
      • ①如果i==j，即指向同一个字符，此时子串一定是回文串；
      • ②如果j-i==1，即两个相同的字符组成的子串，比如aa，此时也是回文串；
      • ③如果j-i>1，即长度大于3的子串，此时是否是回文串取决于dp[i+1][j-1]。
    • 如果s[i]!=s[j]，以[i,j]为范围的子串一定不是回文串，所以dp[i][j]=false。
  • 初始化：注意一下boolean数组默认初始都为true。我们在初始化时要都初始化成false，不然都成回文串了。也就是说初始化时我们默认都不是回文串，要通过我们递推公式的判断来最终确定是不是回文串。
  • ★遍历顺序：从递推公式情况③可以看出，dp[i][j]是根据dp[i + 1][j - 1]是否为true再进行赋值的，而dp[i + 1][j - 1] 在 dp[i][j]的左下角(如下图)，所以说我们要先得到左下角，才能推出右下角，因此遍历顺序必须是从下往上、从左往右。
    

    public int countSubstrings(String s) {
        int res=0;
        boolean[][] dp=new boolean[s.length()][s.length()];
        for(int i=0;i<dp.length;i++){
            for(int j=0;j<dp[0].length;j++){
                dp[i][j]=false;
            }
        }
            //★注意遍历顺序！
        for(int i=s.length()-1;i>=0;i--){
            for(int j=i;j<s.length();j++){//★因为我们要的是[i,j]这个范围的子串，所以j一定是大于等于i的。
                if(s.charAt(i)==s.charAt(j)){
                    if(j-i<=1){
                        dp[i][j]=true;
                        res++;
                    }else if(dp[i+1][j-1]==true){
                        dp[i][j]=true;
                        res++;
                    }
                }
                //这里二者不相等的时候不判断也行，因为我们初始化时本来就是false
                // else{
                //     dp[i][j]=false;
                // }
            }
        }
        return res;
    }

• ★思路三：双指针。用dp空间复杂度太高了，我们考虑用双指针来实现。对于"aaababa"来说，我们可以遍历每个元素，以该元素为中心用两个指针往两边扩散，判断是不是回文串，但是要注意这样只能找到单数长度的子串，因此还要以每两个元素为中心向两边扩散，这样找到的就全是双数长度的子串。
  

  class Solution {
      public int countSubstrings(String s) {
          int res=0;
          int len=s.length();
          //单数中心
          for(int i=0;i<len;i++){
              res+=countString(s,i,i);
          }
          //双数中心
          for(int i=0;i<len-1;i++){
              res+=countString(s,i,i+1);
          }
          return res;
      }
      //中心扩散
      public int countString(String s,int left,int right){
          int count=0;
          while(left>=0&&right<s.length()&&s.charAt(left)==s.charAt(right)){
              left--;
              right++;
              count++;
          }
          return count;
      }
  }

• 思路：注意！这道题是子序列(可不连续)！上面那道题是子串，子串必须是连续的，所以这道题不能用中心扩散法了。我们通过dp，还是从s中心
  • 确定dp数组：dp[i][j]：字符串s在[i, j]范围内最长的回文子序列的长度为dp[i][j]。
  • ★递推公式：在判断回文子串的题目中，关键就是看s[i]与s[j]是否相同：
    • 如果s[i]与s[j]相同，那么dp[i][j] = dp[i + 1][j - 1] + 2；
      
      
    • 如果s[i]与s[j]不相同，说明s[i]和s[j]同时加入不是回文串，那么分别加入s[i]、s[j]看看哪一个可以组成最长的回文子序列。
              
              加入s[j]的回文子序列长度为dp[i + 1][j]。
              加入s[i]的回文子序列长度为dp[i][j - 1]。
      那么dp[i][j]一定是取最大的，即：dp[i][j] = max(dp[i + 1][j], dp[i][j - 1])。
  • 初始化：从递推公式dp[i][j] = dp[i + 1][j - 1] + 2可以看出递推公式是计算不到 i 和 j 相同时候的情况，所以要对dp[i][i]进行初始化，此时子串就是一个字符，dp[i][i]=1。
  • ★确定遍历顺序：从递归公式中，可以看出，dp[i][j] 依赖于 dp[i + 1][j - 1] ，dp[i + 1][j] 和 dp[i][j - 1]，所以遍历 i 的时候一定要从下到上遍历，这样才能保证下一行的数据是经过计算的；j 的话，可以正常从左向右遍历。
    
  • 
    

    class Solution {
        public int longestPalindromeSubseq(String s) {
            int len=s.length();
            //dp[i][j]表示s[i,j]这个回文子序列的最大长度
            int[][] dp=new int[len][len];
            //初始化
            for(int i=0;i<len;i++){
                dp[i][i]=1;
            }
            //从下往上、从左往右
            for(int i=len-1;i>=0;i--){
                for(int j=i+1;j<len;j++){//★这里注意j=i+1,因为j=i的情况我们初始化时考虑了
                    if(s.charAt(i)==s.charAt(j)){
                        dp[i][j]=dp[i+1][j-1]+2;
                    }else{
                        dp[i][j]=Math.max(dp[i][j],Math.max(dp[i][j-1],dp[i+1][j]));
                    }
                }
            }
            //返回s[0,len-1]范围内的最长回文子序列的长度
            return dp[0][len-1];
        }
    }

• 思路一：dp。
  • 定义dp数组：dp[i]表示以i结尾的子串的最长有效括号长度。
  • ★★★递推公式：
    • （1）如果ch[i]是(，那么ch[i]一定无法跟前面的组成有效括号，即dp[i]=0;
    • （2）如果ch[i]是)，要根据ch[i-1]进行判断;
              1)如果ch[i-1]是(，那么ch[i-1]和ch[i]刚好组成一对有效括号，也就是说【有效括号的长度+2】，此时dp[i]=dp[i-2]+2;
                  
      

              2)如果ch[i-1]是)，要看s[i]前面有没有和s[i]组成有效括号对的字符，即形如((....))，我们需要找到与s[i]配对的位置★i-dp[i-1]-1，判断该位置是不是(即可，是的话dp[i]=dp[i-1]+2。★匹配位置前面还是匹配上的，此时dp[i]=dp[i-1]+2+dp[i-dp[i-1]-2]。
                  
  • 初始化：无论第一个字符是什么，都有：dp[0] = 0dp[0]=0。

    public int longestValidParentheses(String s) {
        if(s==null) return 0;
        int len=s.length();
        char[] chs=s.toCharArray();
        //dp[i]表示以i结尾的子串的最长有效括号长度
        int[] dp=new int[len];
        //初始化
        //dp[0]=0;
        int res=0;
        for(int i=1;i<len;i++){
            if(chs[i]==')'){
                if(chs[i-1]=='('){//前一个是(
                    if(i<2){//★考虑一开头的位置，主要为了防止dp[i-2]越界
                        dp[i]=2;
                    }else{
                        dp[i]=dp[i-2]+2;
                    }
                }else{//前一个是)
                    if(dp[i-1]>0){//★前一个是有效的，再去看chs[i]的匹配位置能否匹配上
                        int matchIdx=i-dp[i-1]-1;//★chs[i]对应的匹配位置
                        if(matchIdx>=0&&chs[matchIdx]=='('){//匹配位置有效且能匹配上
                            dp[i]=dp[i-1]+2;
                            if(matchIdx-1>0){//★考虑匹配位置前的有效括号
                                dp[i]=dp[i]+dp[matchIdx-1];
                            }
                        }
                    }
                }
            }
            res=Math.max(res,dp[i]);
        }
        return res;
    }

• 思路二：先用栈进行匹配，找到匹配不上的括号，标记为1，然后这个问题就转化成了在标记数组mark中找连续0的最大长度。

  public int longestValidParentheses(String s) {
      if(s==null||"".equals(s)) return 0;
      char[] chs=s.toCharArray();
      int len=s.length();
      //先用栈进行匹配，找出用不上(不匹配)的括号
      Deque<Integer> stack=new ArrayDeque<>();
      //★能用来匹配的括号记为0，不能匹配的记为1
      int[] mark=new int[len];
      for(int i=0;i<len;i++){
          if(chs[i]=='('){
              stack.push(i);//★栈里只进( !
          }else{
              //上来就是右括号，比如)()，那么这个)就是用不上的，标记为1
              if(stack.isEmpty()){
                  mark[i]=1;
              }else{
                  //从栈里出一个(，说明能匹配上
                  stack.pop();
              }
          }
      }
      //将栈中剩的(的mark记为1
      while(!stack.isEmpty()){
          mark[stack.pop()]=1;
      }
      //遍历mark，找连续0的最大长度，即为所求最长有效括号的长度
      int res=0,len0=0;
      for(int i=0;i<len;i++){
          if(mark[i]==1){
              len0=0;
              continue;
          }else{
              len0++;
              res=Math.max(res,len0);
          }
      }
      return res;
  }