一文看清背包套路

发表于 2021-01-08 更新于 2021-01-11 分类于 LeetCode刷题

刷了几道背包问题，用了一周时间，动态规划的难真的领会到了。但再难总有规律可循，总结中刷题，刷题中总结。

关于0-1背包的问题有：

416，分割等和子集
494，目标和
474，一和零

关于完全背包的问题有：

322，零钱兑换

518，零钱兑换Ⅱ
377，组合总和Ⅳ
139，单词拆分

一、0-1背包问题

引入

一个可装载重量为W的背包和N个物品，每个物品有重量和价值两个属性。怎么装使这个背包装下物品的价值最大？

套路：

子问题：二维 dp 数组 $dp[i][j]$—对于前 i 个物品，当前背包容量为 j，这种情况下可以装的最大价值是 $dp[i][j]$。

比如说，如果 $dp[3][5] = 6$，其含义为：对于给定的一系列物品中，若只对前 3 个物品进行选择，当背包容量为 5 时，最多可以装下的价值为 6。根据这个定义，我们想求的最终答案就是 dp[N][W]。
base case：当没有物品或背包没有容量时，$dp[0][...] = dp[...][0] = 0$
状态转移：

物品 i 有两种选择—装进背包和不装，设第 i 件物品体积为 w，价值为 v。
- 物品 i 不装进背包，最大价值 $dp[i][j] = dp[i - 1][j]$
- 物品 i 装进背包，最大价值 $dp[i][j] = dp[i - 1][j - w] + v$
因此，0-1 背包的状态转移方程为：

$dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - w] + v)$

代码：

   // W 为背包总体积
// N 为物品数量
// weights 数组存储 N 个物品的重量
// values 数组存储 N 个物品的价值
   public int knapsack(int W, int N, int[] weight, int[] values){
    //dp[i][j]表示装 i 个物品背包容量为 j
    int[][] dp = new int[N + 1][W + 1];
    //默认初始化都为0，从第1行和第1列开始赋值
    for(int i = 1; i < N + 1; i++){
        //物品从weight[0]开始添加，w表示第i个物品的体积，v表示第i个物品的价值
        int w = weight[i - 1]; int v = values[i - 1];
        for(int j = 1; j < W + 1; j++){
            // 装入或者不装入背包，择优
            if(j >= w)
            	dp[i][j] = Math.max(dp[i - 1][j],dp[i - 1][j - w] + v);
            // 当前背包容量装不下，只能选择不装入背包
            else
                dp[i][j] = dp[i - 1][j];
        }
    }
    return dp[N][W];
}

注意到 $dp[i][j]$ 都是通过上一行 $dp[i-1][..]$ 转移过来的，之前的数据都不会再使用了。所以，我们可以进行状态压缩，将二维 dp 数组压缩为一维，节约空间复杂度，可见下一题。

416，分割等和子集，medium

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

每个数组中的元素不会超过 100 数组的大小不会超过 200 示例 1:

输入: [1, 5, 11, 5]

输出: true

解释: 数组可以分割成 [1, 5, 5] 和 [11].

示例 2:

输入: [1, 2, 3, 5]

输出: false

解释: 数组不能分割成两个元素和相等的子集.

题意分析：

看起来和背包没关系，实际是背包问题的变体：子集背包问题。原背包问题的二维数组 $v = dp[i][j]$ 表示对于前 i 个物品，当前背包容量为 j，这种情况下可以装的最大价值是 $v$。

此题中，要把数组分割成两个等和子集，即背包容量：数组的和 sum的一半，物品：数组元素。如果遍历数组，部分元素的和恰好为背包容量，则剩余元素的和也恰好为 sum / 2，返回true。
思路：

特殊情况：

nums 数组的元素和 sum 若为奇数，则无法分割，返回false。

如果 n < 2，数组无法分割，返回false。

子问题

$x = dp[i][j]$ 表示对于数组nums 的前 i 个元素，当前元素和是否为 j，若为 j ，$x = true$；否则，$x = false$。
base case

$dp[0][...] = false$ 数组中没有元素可选取，返回false。

$dp[...][0] = true$ 目标元素和为 0，不选取元素即可。
状态转移方程

当前元素 num = nums[i - 1]（从数组的第 0 个元素开始遍历）

①. j >= num
- 不将 num 算入，能否恰好等于 j ,$dp[i][j]$取决于 $dp[i - 1][j]$
- 将 num 算入，能否恰好等于 j ,$dp[i][j]$取决于 $dp[i - 1][j - num]$
  
  理解：如果装入第 i 个元素，要看剩余元素和 j - num 限制下是否恰好装满。
②.j < num

要达到的元素和比当前元素值小，无法加入。

总结：

代码:

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        if(n < 2) return false;
        int sum = 0;
        for(int num : nums){
            sum += num;            
        }
        if(sum % 2 != 0) return false;
        int target = sum / 2;
        //dp[i][j]— [0, i]元素 元素是否为 j
        boolean[][] dp = new boolean[n + 1][target + 1];//初始化都为false
        //base case
        for(int i = 0; i < n ; i++){
            dp[i][0] = true;
        }
        for(int i = 1; i < n + 1; i++){
            int num = nums[i - 1];
            for(int j = 1; j < target + 1; j++){
                //要达到的元素和 比 当前元素值 小，无法加入
                if(j < num) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j] | dp[i - 1][j - num];
            }
        }
        return dp[n][target];
    }
}

降维

$dp[i][j]$ 都是通过上一行 $dp[i-1][..]$ 转移过来的，可以进行状态压缩，将二维 dp 数组压缩为一维，但要注意 j 应该从后往前反向遍历，因为每个物品（或者说数字）只能用一次，以免之前的结果影响其他的结果。

代码

class Solution {
  public boolean canPartition(int[] nums) {
      int n = nums.length;
      int sum = 0;
      for(int num : nums){
          sum += num; 
      }
      //特殊：
      if(sum % 2 != 0) return false;
      if(n < 2) return false;
      sum = sum / 2;
      boolean[] dp = new boolean[sum + 1];
      dp[0] = true;
       for(int i = 1; i <= n; i++){
          int num = nums[i - 1];
          for(int j = sum; j > 0; j--){
              if(j >= num)
                  dp[j] = dp[j] | dp[j - num];
          }
      }
      return dp[sum];
  }
}

总结做题步骤：

理解题意，判定此题为 0-1背包问题
此题是否有特殊情况
动态规划正常做法 1. 子问题：确定背包和物品指代什么，$dp[i][j]$ 返回值是什么 2. base case：通常为 $dp[0][...]、dp[...][0]、dp[0][0]$ 3. 状态转移方程：先遍历物品，再遍历背包。每个物品只有装和不装两个选择。
```
组合问题公式   dp[i] += dp[i - num]
True、False问题公式    dp[i] = dp[i] or dp[i - num]
最大最小问题公式    dp[i] = min(dp[i], dp[i - num]+1) 或 dp[i] =  max(dp[i], dp[i - num]+1)
```
最终返回结果
状态压缩至一维（可不进行）

494，目标和，medium

给定一个非负整数数组a1, a2, ..., an 和一个目标数 S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。

返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

示例：

输入：nums: [1, 1, 1, 1, 1], S: 3
输出：5
解释：

-1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3

一共有5种方法让最终目标和为3。

提示：
 数组非空，且长度不会超过 20 。
   初始的数组的和不会超过 1000 。
  保证返回的最终结果能被 32 位整数存下。

题意分析：则转换为 0-1背包问题：给定一个数组和一个容量为 target 的背包，求多少种方式将背包填满。
思路：
1. 子问题
  
  $x = dp[i][j]$ 表示对于数组nums 的前 i 个元素，放进容量 j 的背包，装满方式为 x。
特殊情况：

S + sum 必须为偶数才可分解，S < sum 才可使数组 nums 元素得到 S。

base case

$dp[0][0] = 1$ 没有元素，所以只能不选，和为0
状态转移方程

当前元素 num = nums[i - 1]（从数组的第 0 个元素开始遍历）

①. j >= num

将当前 num = nums[i-1] 放入或不放入背包，$dp[i][j] = dp[i-1][j]+dp[i-1][j-num]$

②. j < num

不能放入，取决于上一状态，$dp[i][j] = dp[i-1][j]$

代码：

class Solution {
  public int findTargetSumWays(int[] nums, int S) {
      int sum = 0;
        for(int num : nums){
            sum += num;
        }
        //特殊情况
        if(S > sum || (sum + S) % 2 == 1) return 0;
       
        int target = (sum + S) / 2;
        int[][] dp = new int[nums.length + 1][target + 1]; 
        //base case
        dp[0][0] = 1;

        // 状态转移方程
        for(int i = 1; i < nums.length + 1; i++){
            int num = nums[i - 1];
            for(int j = 0; j < target + 1; j++){
                if(j >= num)
                    dp[i][j] = dp[i - 1][j] + dp[i - 1][j - num];
                else
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[nums.length][target];
    }
}

对base case 的理解：

注意与0-1背包的区别：

对于0-1 背包，物品大小为正数，可以先对二维数组初始化第0行（除$[0][0]$ 位置外全为0）和第0列（全为1）。然后 i 和 j 都从1开始遍历。对于该问题，列表中可能存在为 0 的元素，因此选不选这个0，都能将容量为0的背包装满。如，nums={0,0},target=0,dp[2][0]≠1。

所以base case 只有 $dp[0][0]=1$, 剩下的第0列的其他位置的值用状态转移方程确定（而不能将 $dp[i][0]$初始化为1）。即 i 从1开始遍历，j 从0开始遍历。

优化：将二维dp数组压缩为一维，dp[i][j]都是通过上一行dp[i-1][..]转移过来的，之前的数据都不会再使用了。需要注意的是 j应该从后往前反向遍历，因为每个物品（数字）只能用一次，以免之前的结果影响其他的结果。

子问题：

$x = dp[i]$ 表示数组 nums 的元素装满容量为 i 的背包，有 x 种装法。
base case

$dp[0] = 1$ 全部不装，一种装法。
状态转移方程

由上面的二维可得$ dp[j] = dp[j] + dp[j - num]$

class Solution {
    public int findTargetSumWays(int[] nums, int S) {
        int sum = 0;
        for(int num : nums){
            sum += num;
        }
        //特殊情况
        if(S > sum || (sum + S) % 2 == 1) return 0;
       
        int target = (sum + S) / 2;
		int[] dp = new int[target + 1]; 
        //base case//放入背包重量为0的方案数为1，不选
        dp[0] = 1;
        for(int i = 1; i < nums.length + 1; i++){
            int num = nums[i - 1];
            for(int j = target; j >= 0; j--){
                if(j >= num)
                    dp[j] = dp[j] + dp[j - num];
            }
        }
        return dp[target];
    }
}

另一种方法：递归

对于第 i 个数，可以 ‘+’ 或 '-'，分别递归搜索两种操作，当搜索完一遍，如果元素和sum等于S，count+1。、

class Solution {
  int count = 0;
  public int findTargetSumWays(int[] nums, int S) {
      return helper(nums, 0, 0, S);
  }
  public int helper(int[] nums, int i, int sum, int S) {
      if(i == nums.length){
          if(sum == S)
              count++;
      }
      else{
          //还没全部搜索完，递归两种情况
          helper(nums, i + 1, sum + nums[i], S);
          helper(nums, i + 1, sum - nums[i], S);
      }
      return count;
  }
}

474，一和零，medium

给你一个二进制字符串数组 strs 和两个整数 m 和 n 。

请你找出并返回 strs 的最大子集的大小，该子集中最多有 m 个 0 和 n 个 1 。

如果 x 的所有元素也是 y 的元素，集合 x 是集合 y 的子集。

示例 1：

输入：strs = ["10", "0001", "111001", "1", "0"], m = 5, n = 3
输出：4
解释：最多有 5 个 0 和 3 个 1 的最大子集是 {"10","0001","1","0"} ，因此答案是 4 。
其他满足题意但较小的子集包括 {"0001","1"} 和 {"10","1","0"} 。{"111001"} 不满足题意，因为它含 4 个 1 ，大于 n 的值 3 。

示例 2：

输入：strs = ["10", "0", "1"], m = 1, n = 1
输出：2
解释：最大的子集是 {"0", "1"} ，所以答案是 2 。

提示：

1 <= strs.length<= 600 1 <= strs[i].length <= 100 strs[i] 仅由 '0' 和 '1' 组成 1 <= m, n <= 100

题目解析：

仍然是 0-1背包问题，但此题的背包有两个，一个放0，一个放1，称为背包0 和背包1。物品：字符串数组中的字符。为最大最小问题。
思路：
1. 子问题
  
  $dp[i][j][k]$ — 前 i 个字符串将背包0容量为 j，背包1容量为k 的最大子集大小
2. base case
  
  $dp[0][...][...]=0$ 如果不使用任何一个字符串，则背包能装的字符串数就为0。
  
  $dp[...][0][0]=0$ 如果背包0，背包1的容量都为0，它能装的字符串数也为0。
3. 状态转移方程
  
  当前字符串str
  - 如果字符串str不装入背包，受上一状态影响。
    
    $dp[i][j][k]=dp[i-1][j][k]$
  - 如果字符串str 装入背包，则与不装入的选择取最大值。
    
    $dp[i][j][k] = max(dp[i-1][j][k],dp[i-1][j-count_0][j-count_1] + 1)$
  边界条件为 j 与 str 中0 的数量的大小关系，k 与 str 中 1 的数量的大小关系。
4. 返回 $dp[len][m][n]$

代码：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][][] dp = new int[len + 1][m + 1][n + 1];
        //base case dp[0][...][...]=0、dp[...][0][0]=0
        
        //先循环物品
        for(int i = 1; i < len + 1; i++){
            String str = strs[i - 1];
            for(int j = 0; j < m + 1; j++){
                for(int k = 0; k < n + 1; k++){
                    if(j < count_0(str) || k < count_1(str))
                    dp[i][j][k] = dp[i - 1][j][k];
                    else
                    dp[i][j][k] = Math.max(dp[i - 1][j][k], dp[i - 1][j - count_0(str)][k - count_1(str)] + 1);
                }
            }
        }
        return dp[len][m][n];
    }
    //统计str中0和1的个数
    public int count_0(String str){
        char[] str_c = str.toCharArray();
        int count = 0;
        for(char c : str_c){
            if(c == '0') count++;
        }
        return count;
    } 
     public int count_1(String str){
        char[] str_c = str.toCharArray();
        int count = 0;
        for(char c : str_c){
            if(c == '1') count++;
        }
        return count;
    } 
}

状态压缩：

class Solution {
    public int findMaxForm(String[] strs, int m, int n) {
        int len = strs.length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i < len + 1; i++){
            String str = strs[i - 1];
            for(int j = m; j >= count_0(str); j--){
                for(int k = n; k >= count_1(str); k--){
                    dp[j][k] = Math.max(dp[j][k], dp[j - count_0(str)][k - count_1(str)] + 1);
                }
            }
        }
        return dp[m][n];
    }
    //统计str中0和1的个数
    public int count_0(String str){
        char[] str_c = str.toCharArray();
        int count = 0;
        for(char c : str_c){
            if(c == '0') count++;
        }
        return count;
    } 
     public int count_1(String str){
        char[] str_c = str.toCharArray();
        int count = 0;
        for(char c : str_c){
            if(c == '1') count++;
        }
        return count;
    } 
}

思考：为什么背包0 和背包1的 j、k要从 0 开始遍历？

字符串数组中如果存在“00”，“00”，选择也是不同的，会影响$dp$ 数组的结果。可参考494题中对 base case 的理解。

0-1背包总结

做题步骤：

理解题意，判定此题为 0-1背包问题
此题是否有特殊情况
动态规划正常做法 1. 子问题：确定背包和物品指代什么，$dp[i][j]$ 返回值是什么 2. base case：通常为 $dp[0][...]、dp[...][0]、dp[0][0]$ 3. 状态转移方程：先遍历物品，再遍历背包。每个物品只有装和不装两个选择。

组合问题公式 dp[i] += dp[i - num] True、False问题公式 dp[i] = dp[i] or dp[i - num] 最大最小问题公式 dp[i] = min(dp[i], dp[i - num]+1) 或 dp[i] = max(dp[i], dp[i - num]+1)
最终返回结果
状态压缩至一维（可不进行）

套模板还是有用的，难的部分在于理清题意再转化到模板。base case 的情况容易混淆，分不清的时候先写出多维dp数组，再进行降维可能还有助于做题。完全背包问题请见下一节总结内容。

二、完全背包问题

完全背包问题引入

完全背包的特点：物品可以无限次选取，且不考虑顺序。
与0-1背包不同在：
- 0-1背包考虑当前物品装入或不装入背包，物品只有一件。
- 完全背包考虑当前物品装入或不装入背包，物品的数量无限，只要背包容量还有剩余就可以一直拿同一种物品。
完全背包的变体问题：物品可以无限次选取，且考虑物品放入的顺序。

下面在具体题目中进行总结。

322，零钱兑换，medium

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

你可以认为每种硬币的数量是无限的。

示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1

示例 2：
输入：coins = [2], amount = 3
输出：-1

示例 3：
输入：coins = [1], amount = 0
输出：0

示例 4：
输入：coins = [1], amount = 1
输出：1

示例 5：
输入：coins = [1], amount = 2
输出：2

提示：

1 <= coins.length <= 12 1 <= coins[i] <= 231 - 1 0 <= amount <= 104

解法一：二维（先遍历物品，再遍历背包）

题目解析：

数组的元素可以使用多次，对顺序没有要求，完全背包问题。
思路：
1. 子问题
  
  $dp[i][j]$ 前 i 个硬币组成总金额 j，所需最少硬币个数。
2. base case
  
  $dp[..][0] = 0$ 金额为0，不取硬币。
  
  特殊情况：
  
  此题中若无法组成总金额，需返回 -1。思考怎么实现呢？
  
  把二维数组 $dp$ 初始化成最大值 amount + 1（硬币面额最少为1），如果发现没更新则说明无法取硬币组成总金额，返回 -1。
3. 递推关系
  
  最小问题，取min。当前coin = coins[i-1]
  - 不选 coin，最少硬币个数不变，总金额不变。
    
    $dp[i][j] = dp[i - 1][j]$
  - 选 coin，最少硬币个数 + 1。因为完全背包问题可以多次选取同一物品，所以为 $dp[i][j - coin]$，与 0-1背包的区别就体现在此。
    
    $dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coin] + 1)$

代码:

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        // 初始化dp表，默认值为极大值，代表无解
        for(int i = 0; i < n + 1; i++){
            Arrays.fill(dp[i], amount + 1);
            //base case
            dp[i][0] = 0;
        }
        for(int i = 1; i < n + 1; i++){
            int coin = coins[i - 1];
            for(int j = 1; j < amount + 1; j++){
                if(j >= coin)
                    dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - coin] + 1);
                else
                     dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][amount] > amount ? -1: dp[n][amount];
    }
}

状态压缩：

class Solution {
    public int coinChange(int[] coins, int amount) {
        int n = coins.length;
        int[] dp = new int[amount + 1];
         Arrays.fill(dp, amount + 1);
        //base case
        dp[0] = 0;
        for(int i = 1; i < n + 1; i++){
            int coin = coins[i - 1];
            for(int j = 1; j < amount + 1; j++){
                if(j >= coin)
                    dp[j] = Math.min(dp[j], dp[j - coin] + 1);
            }
        }
        return dp[amount] > amount ? -1: dp[amount];
    }
}

解法二：一维（先遍历背包，再遍历物品）

题目解析：

数组的元素可以使用多次，对顺序没有要求，完全背包问题。
思路：
1. 子问题
  
  $dp[i]$ 硬币组成金额为 i ，所需最少硬币个数。
2. base case
  
  $dp[0] = 0$ 金额为0，不取硬币。
3. 递推关系
  
  以 coins=[1,2,5] amount = 11 为例
  
  k 枚硬币 a1，... ,ak 总和为 11，即 $dp[11] = k$，上一状态就是 $dp[11-ak] = k-1$
  
  状态转移方程为：
  
  $dp[i]=min(dp[i-coin])+1$，for coin in coins and if i >= coin

代码：

class Solution {
    public int coinChange(int[] coins, int amount) {
        //特殊判断，可有可无
        if(coins.length == 1 && amount % coins[0] != 0)
            return -1;
              
        int[] dp = new int[amount + 1];
        //硬币面额至少为1，最多为amount
        Arrays.fill(dp, amount + 1);
        dp[0] = 0;
        //外循环为dp数组从1开始的值
        for(int i = 1; i < amount + 1; i++){
            //内循环为 coins 数组元素值
            for(int j = 0; j < coins.length; j++){
                int coin = coins[j];
                if(i >= coin)
                    //得到上一状态的最小值
                    dp[i] = Math.min((dp[i - coin] + 1), dp[i]);
            }
        } 
       //如果dp[amount]没更新，返回-1
        return dp[amount] > amount ? -1: dp[amount];
    }
}

518，零钱兑换Ⅱ，medium

给定不同面额的硬币和一个总金额。写出函数来计算可以凑成总金额的硬币组合数。假设每一种面额的硬币有无限个。示例 1:

输入: amount = 5, coins = [1, 2, 5]
输出: 4
解释: 有四种方式可以凑成总金额:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

示例 2:

输入: amount = 3, coins = [2]
输出: 0
解释: 只用面额2的硬币不能凑成总金额3。

示例 3:

输入: amount = 10, coins = [10] 
输出: 1

注意:

你可以假设：

0 <= amount (总金额) <= 5000 1 <= coin (硬币面额) <= 5000 硬币种类不超过 500 种结果符合 32 位符号整数

题目解析：

数组的元素可以使用多次，对顺序没有要求，完全背包问题。组合问题。
思路：
1. 子问题
  
  $dp[i][j]$ — 前 i 个硬币组成金额 j 的组合数。
2. base case
  
  $dp[..][0] = 1$ 全部都不拿，只有这一种拿法。
3. 递推关系
  
  $dp[i][j]$ 取决于是否选择 coin = coins[i-1]
  - 如果不选（即不将 coin 装入背包），$dp[i][j] = dp[i - 1][j]$
  - 如果选（即将 coin 装入背包），$dp[i][j] = dp[i][j-coin]$，注意此处与 0-1背包不同，硬币还可再选取。
  要得到总的组合数，状态转移方程为：
  
  $dp[i][j] = dp[i - 1][j] + dp[i][j-coin]$

代码：

class Solution {
    public int change(int amount, int[] coins) {
        int n = coins.length;
        int[][] dp = new int[n + 1][amount + 1];
        for(int i = 0; i < n + 1; i++)
            dp[i][0] = 1;

        for(int i = 1; i < n + 1; i++){
            int coin = coins[i - 1];
            for(int j = 1; j < amount + 1; j++){
                if(j >= coin)
                    dp[i][j] = dp[i - 1][j] + dp[i][j - coin];
                else 
                    dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][amount];
    }
}

状态压缩：通过观察可以发现，dp数组的转移只和dp[i][..]和dp[i-1][..]有关，所以可以压缩状态，进一步降低算法的空间复杂度。

class Solution {
    public int change(int amount, int[] coins) {
		int n = coins.length;
        int[] dp = new int[amount + 1];
        dp[0] = 1;
        for(int i = 1; i < n + 1; i++){
            int coin = coins[i - 1];
            for(int j = 1; j < amount + 1; j++){
                if(j >= coin)
                    dp[j] += dp[j - coin];
            }
        }
        return dp[amount];
    }
}

下面两题为完全背包的变体：物品可以无限次选取，且考虑物品放入背包的顺序。

377，组合总和Ⅳ，medium

给定一个由正整数组成且不存在重复数字的数组，找出和为给定目标正整数的组合的个数。

示例:

nums = [1, 2, 3]
target = 4

所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意，顺序不同的序列被视作不同的组合。
因此输出为 7。

题意分析

完全背包问题的变体：

数组的每个元素可以使用多次，直到等于target。

不同于完全背包：顺序不同的序列被视作不同的组合。
思路：
1. 子问题
  
  $dp[i]$ —数组的元素组合为 i 的个数。
2. base case
  
  $dp[0] = 1$ 所有数都不选，只有一种。
3. 状态转移方程
  
  image.png
  
  以 nums =[1,2,3]，target = 4 为例，
  
  在这里插入图片描述
  
  即将 target = 4 拆分为 nums[i] 和 dp[target - nums[i]]，最终得到 $dp[4] = dp[3] + dp[2] + dp[1]$
  
  则状态转移方程为：
  
  $dp[i] = sum(dp[i - num])$ for num in nums and if i >= num

代码：

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int n = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;
        for(int i = 1; i < target + 1; i++){
            for(int num : nums){
                if(num <= i){
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}

139，单词拆分，medium

给定一个非空字符串 s 和一个包含非空单词的列表 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

拆分时可以重复使用字典中的单词。你可以假设字典中没有重复的单词。示例 1：

输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

题意分析

完全背包问题的变体：物品(wordDict中的单词)可以无限使用，直到填满背包（字符串s）。TRUE / False 问题。
思路
1. 子问题
  
  $dp[i]$ 字符串前 i 个字符组成的字符串 s[0,i-1] 能否拆分为 wordList 中的单词
2. base case
  
  $dp[0] = 0$ 表示空串且合法。
3. 递推关系
  
  对于物品（wordDict 中的单词），要求有顺序放入背包（字符串s），则将物品迭代置于内循环，将背包迭代放在外循环，这样才能让物品按一定顺序放入背包中。
  
  如果有单词等于字符串s的一部分，需要检查后面的字符串是否能放入背包。
  
  $dp[i] = dp[i] | dp[i - len];$

代码：

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        //s 为背包
        int n = s.length();
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;

        for(int i = 1; i < n + 1; i++){
            for(String word : wordDict){
                int len = word.length();
                if(i >= len && word.equals(s.substring(i-len, i)))
                    dp[i] = dp[i] | dp[i - len];
            }
        }
        return dp[n];
    }
}

完全背包问题总结

做题步骤：

理解题意，判定此题为完全背包问题或完全背包问题的变体。根据所求分为组合问题，True/False问题，最大最小问题。通常用一维 $dp$ 数组解题。
此题是否有特殊情况
动态规划正常做法
1. 子问题：确定背包和物品指代什么，$dp[i]$ 返回值是什么
  1. base case：通常为 $dp[0]$
2. 状态转移方程： 先遍历背包，再遍历物品。这样才能保证放入顺序。
组合问题公式 dp[i] += dp[i - num] True/False问题公式 dp[i] = dp[i] or dp[i - num] 最大最小问题公式 dp[i] = min(dp[i], dp[i - num]+1) 或 dp[i] = max(dp[i], dp[i - num]+1)
最终返回结果

------ 本文结束感谢您的阅读 ------