动态规划（Dynamic Programming）解题步骤

五步走：

  1. 确定dp数组（dp table）以及下标的含义。
  2. 确定递推公式
  3. dp数组如何初始化
  4. 确定遍历顺序

  5. 举例推导dp数组

    力扣题目

    509. 斐波那契数

    力扣题目链接
    使用一维dp数组来存结果

  6. 确定dp数组及其下标的含义

dp[i]表示在斐波那契数列中的第i个数

  1. 确定递推公式

状态转移方程：dp[i] = dp[i - 1] + dp[i - 2]

  1. dp数组如何初始化

题目中已经给出了

  1. dp[0] = 0;
  2. dp[1] = 1;
  1. 确定遍历顺序

从递推公式可以看出，当前结果是需要上两个的结果，所以遍历顺序是从前往后的。

  1. 举例推导dp数组

    1. [0, 1, 1, 2, 3, 5, 8, 13]

    题解

    1. class Solution {
    2.  public int fib(int n) {
    3.      if (n == 0 || n == 1) return n;
    4.      int[] dp = new int[n + 1];
    5.      dp[0] = 0;
    6.      dp[1] = 1;
    7.      for (int i = 2; i <= n; i++) {
    8.          dp[i] =dp[i - 1] + dp[i - 2];
    9.      }
    10.      return dp[n];
    12.  }
    13. }

    70. 爬楼梯

    力扣题目链接

    题解

    1. class Solution {
    2.  public int climbStairs(int n) {
    3.      if (n <= 2) return n; 
    5.      int[] dp = new int[n + 1];
    6.      dp[1] = 1;
    7.      dp[2] = 2;
    8.      for (int i = 3; i <= n; i++) {
    9.          dp[i] = dp[i - 1] + dp[i - 2];
    10.      }
    11.      return dp[n];
    12.  }
    13. }

    62.不同路径

    力扣题目链接

  2. 确定dp数组（dp table）以及下标的含义

dp[i][j]表示从起点（0，0）到点（i，j）的路径数

  1. 确定递推公式

dp[i][j] = dp[i - 1][j] + dp[i][j - 1]
由于我们每一步只能从向下或者向右移动一步，因此要想走到 (i,j)，如果向下走一步，那么会从(i−1,j) 走过来；如果向右走一步，那么会从 (i, j-1) 走过来。

  1. dp数组如何初始化

dp[i][0]都是1，只能往下走。同理dp[0][j]都是1，只能往右走。

  1. 确定遍历顺序

遍历二维数组的方式，两层for循环，从左往右。

  1. 举例推导dp数组

    题解

    1. class Solution {
    2.  public int uniquePaths(int m, int n) {
    3.      int[][] dp = new int[m][n];
    4.      //初始化
    5.      for (int i = 0; i < m; i++) {
    6.          dp[i][0] = 1;
    7.      }
    8.      for (int j = 0; j < n; j++) {
    9.          dp[0][j] = 1;
    10.      }
    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.      }
    18.      return dp[m - 1][n - 1];
    20.  }
    21. }

    63. 不同路径 II

    力扣题目链接

  2. 确定dp数组及其下标的含义

dp[i][j]从起点（0，0）出发到（i，j）有dp[i][j]条不同的路径。

  1. 确定递推公式

和上一题一样，dp[i][j] = dp[i - 1][j] + dp[i][j - 1]但前提是该点没有障碍物

  1. 初始化

对于（0，0）到（i，0）和（0，0）到（0，j）在遇到障碍物之前都是1，障碍物之后的都为0。
java数组初始化的默认值为0.

  1. 遍历顺序

二维数组的遍历方式，从左到右，自上到下。

题解

  1. class Solution {
  2.     public int uniquePathsWithObstacles(int[][] obstacleGrid) {
  3.         int m = obstacleGrid.length;
  4.         int n = obstacleGrid[0].length;
  5.         int[][] dp = new int[m][n];
  7.         for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) dp[i][0] = 1;
  8.         for (int j = 0; j < n && obstacleGrid[0][j] == 0; j++) dp[0][j] = 1;
  10.         for (int i = 1; i < m; i++) {
  11.             for (int j = 1; j < n; j++) {
  12.                 if (obstacleGrid[i][j] ！= 1) {
  13.                     dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
  14.                 }
  15.             }
  16.         }
  18.         return dp[m - 1][n - 1];
  19.     }
  20. }

343. 整数拆分

力扣题目链接

  1. 确定dp数组（dp table）以及下标的含义。

dp[i]表示拆分i，使其得到的最大乘积为dp[i]。

  1. 确定递推公式
  • 当 i ≥ 2 时，假设对正整数 i 拆分出的第一个正整数是 j（1 ≤ j < i），则有以下两种方案：

将 i 拆分成 j 和 i - j 的和，且 i − j 不再拆分成多个正整数，此时的乘积是 j × (i − j) ；
将 i 拆分成 j 和 i − j 的和，且 i − j 继续拆分成多个正整数，此时的乘积是 j × dp[i − j] 。
因此，当 j 固定时，有 dp[i] = max( j × (i − j), j × dp[i − j])。由于 j 的取值范围是 1 到 i − 1 ，需要遍历所有的 j 得到dp[i]。

  1. dp数组如何初始化

题目要求n >= 2，让dp[2] = 1就可以了。i从三开始遍历

  1. 确定遍历顺序

两层for循环，从左往右开始遍历。

题解

  1. class Solution {
  2.     public int integerBreak(int n) {
  3.         int[] dp = new int[n + 1];
  4.         dp[2] = 1;
  6.         for (int i = 3; i <= n; i++) {
  7.             for (int j = 1; j < i; j++) {
  8.                 dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
  9.             }
  10.         }
  11.         return dp[n];
  13.     }
  14. }

01背包问题

有n件物品和一个最多能背重量为w 的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品只能用一次，求解将哪些物品装入背包里物品价值总和最大。

背包最大重量为4。
物品为：

重量 价值
物品0 1 15
物品1 3 20
物品2 4 30 
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagsize = 4;

问背包能背的物品最大价值是多少？

二维数组表示

  1. 确定dp数组（dp table）以及下标的含义。

dp[i][j]表示：从下标为[0 ，i]的物品里任选，放进容积为 j 的背包，价值总和最大。（注意 i 的定义）

  1. 确定递推公式
  • dp[i - 1][j]

无法继续放入了，物品 i 的重量大于背包 j 的重量了。

  • dp[i - 1][j - weight[i]] + value[i]

可以继续放入，dp[i - 1][j - weight[i]] 为背包容量为j - weight[i]的时候不放物品i的最大价值，那么dp[i - 1][j - weight[i]] + value[i] （物品i的价值），就是背包放物品i得到的最大价值。

  • 递推公式

dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);

  1. dp数组如何初始化

image.png

  • 当背包重量 j 为0时，第0列肯定为0。（这个不用手动初始化，创建的二维数组初始值全为0）
  • 状态转移方程 dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]); 可以看出i 是由 i-1 推导出来，那么i为0的时候就一定要初始化。

dp[0][j]，即：i为0，存放编号0的物品的时候，各个容量的背包所能存放的最大价值。
那么很明显当 j < weight[0]的时候，dp[0][j] 应该是 0，因为背包容量比编号0的物品重量还小。
当j >= weight[0]时，dp[0][j] 应该是value[0]，因为背包容量放足够放编号0物品。

for (int j = 0; j < weight[0]; i++) { //其实可以省略，dp数组初始化的值为0
    dp[0][j] = 0;
}

for (int j = weight[0]; j <= bagweight; j+=) {
    dp[0][j] = value[0];
}
  1. 确定遍历顺序

先遍历物品然后背包重量。

for (int i = 1; i < weigth.length; i++) {
    for (int j = 0; j <= bageweight; j++) {
        if (j < weight[i]) dp[i][j] = dp[i - 1][j];
        else dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i]] + value[i]);
    }
}

    public static void main(String[] args) {
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        int bagsize = 4;
        testweightbagproblem(weight, value, bagsize);
    }

    public static void testweightbagproblem(int[] weight, int[] value, int bagsize){
        int wlen = weight.length, value0 = 0;
        //定义dp数组：dp[i][j]表示背包容量为j时，前i个物品能获得的最大价值
        int[][] dp = new int[wlen + 1][bagsize + 1];
        //初始化：背包容量为0时，能获得的价值都为0
        for (int i = 0; i <= wlen; i++){
            dp[i][0] = value0;
        }
        //遍历顺序：先遍历物品，再遍历背包容量
        for (int i = 1; i <= wlen; i++){
            for (int j = 1; j <= bagsize; j++){
                if (j < weight[i - 1]){
                    dp[i][j] = dp[i - 1][j];
                }else{
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i - 1][j - weight[i - 1]] + value[i - 1]);
                }
            }
        }
        //打印dp数组
        for (int i = 0; i <= wlen; i++){
            for (int j = 0; j <= bagsize; j++){
                System.out.print(dp[i][j] + " ");
            }
            System.out.print("\n");
        }
    }

一维数组表示

  1. 确定dp数组的定义

在一维dp数组中，dp[j]表示：容量为j的背包，所背的物品价值可以最大为dp[j]。

  1. 一维dp数组的递推公式

dp[j]为 容量为j的背包所背的最大价值，那么如何推导dp[j]呢？
dp[j]可以通过dp[j - weight[i]]推导出来，dp[j - weight[i]]表示容量为j - weight[i]的背包所背的最大价值。
dp[j - weight[i]] + value[i] 表示 容量为 j - 物品i重量 的背包 加上 物品i的价值。（也就是容量为j的背包，放入物品i了之后的价值即：dp[j]）
此时dp[j]有两个选择，一个是取自己dp[j] 相当于 二维dp数组中的dp[i-1][j]，即不放物品i，一个是取dp[j - weight[i]] + value[i]，即放物品i，指定是取最大的，毕竟是求最大价值，
所以递归公式为：

dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
  1. 初始化

dp[0]是肯定为0的，根据递推公式来看，dp[j]一定是取最大的值，其余也就初始化为0。

  1. 遍历顺序

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

 }
}

    二维dp遍历的时候，背包容量是从小到大，而一维dp遍历的时候，背包是从大到小。
    为什么呢？
    倒序遍历是为了保证物品i只被放入一次！。但如果一旦正序遍历了，那么物品0就会被重复加入多次！

     public static void main(String[] args) {
     int[] weight = {1, 3, 4};
     int[] value = {15, 20, 30};
     int bagWight = 4;
     testWeightBagProblem(weight, value, bagWight);
 }

 public static void testWeightBagProblem(int[] weight, int[] value, int bagWeight){
     int wLen = weight.length;
     //定义dp数组：dp[j]表示背包容量为j时，能获得的最大价值
     int[] dp = new int[bagWeight + 1];
     //遍历顺序：先遍历物品，再遍历背包容量
     for (int i = 0; i < wLen; i++){
         for (int j = bagWeight; j >= weight[i]; j--){
             dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
         }
     }
     //打印dp数组
     for (int j = 0; j <= bagWeight; j++){
         System.out.print(dp[j] + " ");
     }
 }

    416. 分割等和子集

    力扣题目链接
    01背包问题。有N件物品和一个最多能放W重量的包。第i件物品的重量是weight[i]，价值是value[i]。每件物品只能用一次，求解哪些物品放入背包后得到的价值总和最大。
    一个物品可以多次放入就是完全背包，一个物品只能使用一次就是01背包。

  2. 确定dp数组（dp table）以及下标的含义。

dp[j]：背包容积为j，最大凑成的j的子集的和为dp[j]。

  1. 确定递推公式

01背包的递推公式为：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
本题，相当于背包里放入数值，那么物品i的重量是nums[i]，其价值也是nums[i]。
所以递推公式：dp[j] = max(dp[j], dp[j - nums[i]] + nums[i]);

  1. dp数组如何初始化

如果如果题目给的价值都是正整数那么非0下标都初始化为0就可以了，如果题目给的价值有负数，那么非0下标就要初始化为负无穷。

  1. 确定遍历顺序

物品遍历的for循环放在外层，遍历背包的for循环放在内层，且内层for循环倒序遍历。

  • 背包的体积为sum/2.
  • 背包放入的物品的重量和价值都是相对应的数组元素。
  • dp[sum/2] = sum/2说明找到满足题目的解。

  • 每个物品只能使用一次。

    题解

    class Solution {
  public boolean canPartition(int[] nums) {

      int sum = 0;
      for (int i : nums) {
          sum += i;
      }
      int[] dp = new int[sum / 2 + 1];
      if (sum % 2 == 1) return false; //总和为奇数肯定不能平分

      for (int i = 0; i < nums.length; i++) {
          for (int j = sum / 2; j >= nums[i]; j--) {
              dp[j] = Math.max(dp[j], dp[j - nums[i]] + nums[i]);
          }
      }

      return dp[sum / 2] == sum / 2;
  }
}

    494. 目标和

    力扣题目链接
    01f8bad2bf6d58c17066921df180b7a.jpg

  1. 确定dp数组（dp table）以及下标的含义。

dp[ j ]：装满容积为 j 的背包，一共有dp[ j ]种方法

  1. 确定递推公式

求组合类问题的公式，大体如下

dp[j] = dp[j - nums[i]]

  1. dp数组如何初始化

    //要是为0的话，递归的结果都是0。可以解释为装满容量为0的背包用一种方法，就是装0件物品（虽然有点牵强，哈哈）
dp[0] = 1

  2. 确定遍历顺序

两层for循环，最外层正序，内层倒序

题解

class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        int sum = 0;
        for (int i : nums) {
            sum += i;
        }
        int n = (sum + target) / 2;
        if (n < 0) n = - n; 

        if ((sum + target) % 2 != 0) return 0;

        int[] dp = new int[n + 1];
        dp[0] = 1;

        for (int i = 0; i < nums.length; i++) {
            for (int j = n; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[n];
    }
}

474.一和零

力扣题目链接

  1. 确定dp数组（dp table）以及下标的含义

dp[i][j]：最多有i个0和j个1的strs的最大子集的大小为dp[i][j]。

  1. 确定递推公式

dp[i][j] 可以由前一个strs里的字符串推导出来，strs里的字符串有zeroNum个0，oneNum个1。
dp[i][j] 就可以是 dp[i - zeroNum][j - oneNum] + 1。
然后我们在遍历的过程中，取dp[i][j]的最大值。
所以递推公式：dp[i][j] = max(dp[i][j], dp[i - zeroNum][j - oneNum] + 1);
01背包的递推公式：dp[j] = max(dp[j], dp[j - weight[i]] + value[i]);
对比一下就会发现，字符串的zeroNum和oneNum相当于物品的重量（weight[i]），字符串本身的个数相当于物品的价值（value[i]）。