[算法] 动态程序设计类 (2) - 01 背包 + 完整背包（注释）

目录

一、理论基础

1. 问题类型

2. 01背包问题

3. 完全背包问题

4. 解题步骤

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

（2）确定递推公式。

（3）dp数组如何初始化。

（4）确定遍历顺序。

（5）举例推导dp数组。

二、Leetcode 题目

1. 分割等和子集

2. 最后一块石头的重量II

3. 目标和

4. 一和零

5. 零钱兑换II

6. 组合总和 Ⅳ

7. 零钱兑换

8. 完全平方数

9. 单词拆分

三、总结

1. 01背包问题

2. 完全背包问题

---

一、理论基础

1. 问题类型

2. 01背包问题

        使用二维数组，其中有两个维度需要分别表示：物品 和 背包容量。

        这里 i 来表示物品、j 表示背包容量。（如果想用 j 表示物品，j 表示背包容量都可以的）

---

        改进：如果把 dp[i - 1] 那一层拷贝到 dp[i] 上，表达式完全可以是：dp[i][j] = max(dp[i][j], dp[i][j - weight[i]] + value[i]); 与其把 dp[i - 1] 这一层拷贝到 dp[i] 上，不如只用一个一维数组了，只用 dp[j]（一维数组，也可以理解是一个滚动数组）。

3. 完全背包问题

        完全背包 和 01背包问题 唯一不同的地方就是，每种物品有无限件。

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

4. 解题步骤

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

（2）确定递推公式。

（3）dp数组如何初始化。

（4）确定遍历顺序。

（5）举例推导dp数组。

二、Leetcode 题目

1. 分割等和子集

https://leetcode.cn/problems/partition-equal-subset-sum/description/https://leetcode.cn/problems/partition-equal-subset-sum/description/

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

示例 1：
输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：
输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

理解：

      ① dp[j] 表示 背包总容量（所能装的总重量）是 j，放进物品后，背的最大重量为 dp[j]。那么如果背包容量为 target， dp[target] 就是装满 背包之后的重量，所以 当 dp[target] == target 的时候，背包就装满了。

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

      ③ dp[0] 一定是 0。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }

        if (sum % 2 == 1) return false;
        int target = sum / 2;
        vector<int> dp(10001, 0);
        for (int i = 0; i < nums.size(); i++) {
            for (int j = target; j >= nums[i]; j--) {
                dp[j] = max(dp[j], nums[i] + dp[j - nums[i]]);
            }
        }

        if (dp[target] == target) return true;
        return false;
    }
};

2. 最后一块石头的重量II

https://leetcode.cn/problems/last-stone-weight-ii/description/https://leetcode.cn/problems/last-stone-weight-ii/description/

        有一堆石头，用整数数组 stones 表示。其中 stones[i] 表示第 i 块石头的重量。

        每一回合，从中选出任意两块石头，然后将它们一起粉碎。假设石头的重量分别为 x 和 y，且 x <= y。那么粉碎的可能结果如下：

• 如果 x == y，那么两块石头都会被完全粉碎；
• 如果 x != y，那么重量为 x 的石头将会完全粉碎，而重量为 y 的石头新重量为 y-x。

        最后，最多只会剩下一块 石头。返回此石头 最小的可能重量 。如果没有石头剩下，就返回 0。

示例 1：
输入：stones = [2,7,4,1,8,1]
输出：1
解释：
组合 2 和 4，得到 2，所以数组转化为 [2,7,1,8,1]，
组合 7 和 8，得到 1，所以数组转化为 [2,1,1,1]，
组合 2 和 1，得到 1，所以数组转化为 [1,1,1]，
组合 1 和 1，得到 0，所以数组转化为 [1]，这就是最优值。

示例 2：
输入：stones = [31,26,33,21,40]
输出：5

理解：

     ① 本题中，石头的重量是 stones[i]，石头的价值也是 stones[i] ，可以 “最多可以装的价值为 dp[j]” == “最多可以背的重量为dp[j]”

     ② 本题为：dp[j] = max(dp[j], dp[j - stones[i]] + stones[i]);

     ③ 提示中给出 1 <= stones.length <= 30，1 <= stones[i] <= 100，所以最大重量就是 30 * 100 。所以 dp 数组开到 1500 大小就可以了。

class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        vector<int> dp(3001, 0);
        int sum = 0;
        for (int i = 0; i < stones.size(); i++) {
            sum += stones[i];
        }
        int target = sum / 2;   // 将石头分成两堆，计算两堆的最小差
        for (int i = 0; i < stones.size(); i++) {
            for (int j = target; j >= stones[i]; j--) {
                dp[j] = max(dp[j], stones[i] + dp[j - stones[i]]);
            }
        }
        return sum - dp[target] - dp[target];
    }
};

3. 目标和

https://leetcode.cn/problems/target-sum/description/https://leetcode.cn/problems/target-sum/description/

        给你一个非负整数数组 nums 和一个整数 target 。向数组中的每个整数前添加 '+' 或 '-' ，然后串联起所有整数，可以构造一个 表达式 ：

• 例如，nums = [2, 1] ，可以在 2 之前添加 '+' ，在 1 之前添加 '-' ，然后串联起来得到表达式 "+2-1" 。

返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。

示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 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
+1 + 1 + 1 + 1 - 1 = 3

示例 2：
输入：nums = [1], target = 1
输出：1

理解：

     ① dp[i][j]：使用 下标为 [0, i] 的 nums[i] 能够凑满 j（包括 j）这么大容量的包，有 dp[i][j] 种方法。

     ② 本题中，物品i的容量是 nums[i]，价值也是 nums[i]。

• 不放物品 i：即背包容量为 j，里面不放 物品 i，装满有 dp[i - 1][j] 中方法。

• 放物品 i： 即：先空出物品i的容量，背包容量为（ j - 物品 i 容量），放满背包有 dp[i - 1][j - 物品i容量] 种方法。

递推公式：dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i]];

class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
        }
        if (abs(target) > sum || (target + sum) % 2 == 1) return 0;
        
        int bagsum = (target + sum) / 2;
        vector<int> dp(bagsum + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = bagsum; j >= nums[i]; j--) {
                dp[j] += dp[j - nums[i]];
            }
        }
        return dp[bagsum];
    }
};

4. 一和零

https://leetcode.cn/problems/ones-and-zeroes/description/https://leetcode.cn/problems/ones-and-zeroes/description/

        给你一个二进制字符串数组 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 。

理解：

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

     ② 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);

     ③ dp 数组初始化为 0

class Solution {
public:
    int findMaxForm(vector<string>& strs, int m, int n) {
        // 多重背包问题（m:0. n:1）
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
        for (string str: strs) {
            int oneNum = 0, zeroNum = 0;
            for (int i = 0; i < str.size(); i++) {
                if (str[i] == '0') zeroNum++;
                else oneNum++;
            }
            for (int i = m; i >= zeroNum; i--) {
                for (int j = n; j >= oneNum; j--) {
                    dp[i][j] = max(dp[i][j], 1 + dp[i - zeroNum][j - oneNum]);
                }
            }
        }
        return dp[m][n];
    }
};

---

5. 零钱兑换II

https://leetcode.cn/problems/coin-change-ii/description/https://leetcode.cn/problems/coin-change-ii/description/

        给你一个整数数组 coins 表示不同面额的硬币，另给一个整数 amount 表示总金额。

        请你计算并返回可以凑成总金额的硬币组合数。如果任何硬币组合都无法凑出总金额，返回 0 。

        假设每一种面额的硬币有无限个。 

        题目数据保证结果符合 32 位带符号整数。

示例 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

理解：

     ① dp[j]：凑成总金额j的货币组合数为 dp[j]。

     ② dp[j] 就是所有的 dp[j - coins[i]]（考虑 coins[i] 的情况）相加。所以递推公式：dp[j] += dp[j - coins[i]];

     ③ dp[0] 一定要为 1。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount + 1, 0);
        dp[0] = 1;
        for (int i = 0; i < coins.size(); i++) { // 遍历物品
            for (int j = coins[i]; j <= amount; j++) { // 遍历背包
                if (dp[j] < INT_MAX - dp[j - coins[i]]) {
                    dp[j] += dp[j - coins[i]];
                }
            }
        }
        return dp[amount];
    }
};

6. 组合总和 Ⅳ

https://leetcode.cn/problems/combination-sum-iv/description/https://leetcode.cn/problems/combination-sum-iv/description/

        给你一个由 不同 整数组成的数组 nums ，和一个目标整数 target 。请你从 nums 中找出并返回总和为 target 的元素组合的个数。

        题目数据保证答案符合 32 位整数范围。

示例 1：
输入：nums = [1,2,3], target = 4
输出：7
解释：
所有可能的组合为：
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
请注意，顺序不同的序列被视作不同的组合。

示例 2：
输入：nums = [9], target = 3
输出：0

理解：

     ① dp[i]: 凑成目标正整数为i的排列个数为 dp[i]

     ② dp[i]（考虑 nums[j]）可以由 dp[i - nums[j]]（不考虑 nums[j]） 推导出来。因为只要得到 nums[j]，排列个数 dp[i - nums[j]]，就是 dp[i] 的一部分。

     ③ 因为递推公式 dp[i] += dp[i - nums[j]] 的缘故，dp[0] 要初始化为 1。

class Solution {
public:
    int combinationSum4(vector<int>& nums, int target) {
        vector<int> dp(target + 1, 0);
        dp[0] = 1;
        for (int i = 0; i <= target; i++) {
            for (int j = 0; j < nums.size(); j++) {
                if (i - nums[j] >= 0 && dp[i] < INT_MAX - dp[i - nums[j]]) {
                    dp[i] += dp[i - nums[j]];
                }
            }
        }
        return dp[target];
    }
};

7. 零钱兑换

https://leetcode.cn/problems/coin-change/description/https://leetcode.cn/problems/coin-change/description/

        给你一个整数数组 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

理解：

     ① dp[j]：凑足总额为 j 所需钱币的最少个数为 dp[j]

     ② 凑足总额为 j - coins[i] 的最少个数为 dp[j - coins[i]]，那么只需要加上一个钱币coins[i] 即 dp[j - coins[i]] + 1就是 dp[j]（考虑 coins[i]）所以 dp[j] 要取所有 dp[j - coins[i]] + 1 中最小的。

        递推公式：dp[j] = min(dp[j - coins[i]] + 1, dp[j]);

     ③ 凑足总金额为 0 所需钱币的个数一定是 0，那么 dp[0] = 0;

// 写法一：（背包在外层循环）
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;  // 0 可以被 0 填充
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.size(); j++) {
                if (i - coins[j] >= 0 && dp[i - coins[j]] != INT_MAX) {
                    dp[i] = min(dp[i - coins[j]] + 1, dp[i]);
                }
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};


// 写法二：（物品在外层循环）
class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, INT_MAX);
        dp[0] = 0;  // 0 可以被 0 填充
        for (int i = 0; i < coins.size(); i++) {
            for (int j = coins[i]; j <= amount; j++) {
                if (dp[j - coins[i]] != INT_MAX) {
                    dp[j] = min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        if (dp[amount] == INT_MAX) return -1;
        return dp[amount];
    }
};

8. 完全平方数

https://leetcode.cn/problems/perfect-squares/description/https://leetcode.cn/problems/perfect-squares/description/

        给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

        完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：
输入：n = 12
输出：3 
解释：12 = 4 + 4 + 4

示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9

理解：

     ① dp[j]：和为 j 的完全平方数的最少数量为 dp[j]。

     ② dp[j] 可以由 dp[j - i * i] 推出， dp[j - i * i] + 1 便可以凑成 dp[j]。此时我们要 选择最小的 dp[j]，所以递推公式：dp[j] = min(dp[j - i * i] + 1, dp[j]);

     ③ dp[0] 表示 和为 0 的完全平方数的 最小数量，那么 dp[0] 一定是 0。非 0 下标的 dp[j]一定要初始为最大值，这样 dp[j] 在递推的时候才不会被初始值覆盖。

// 写法一：（现遍历背包）
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) {  // 遍历背包
            for (int j = 1; j * j <= i; j++) {  // 遍历物品
                dp[i] = min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
};


// 写法二：（现遍历物品）
class Solution {
public:
    int numSquares(int n) {
        vector<int> dp(n + 1, INT_MAX);
        dp[0] = 0;
        for (int i = 1; i * i <= n; i++) { // 遍历物品
            for (int j = i * i; j <= n; j++) { // 遍历背包
                dp[j] = min(dp[j - i * i] + 1, dp[j]);
            }
        }
        return dp[n];
    }
};

9. 单词拆分

https://leetcode.cn/problems/word-break/description/https://leetcode.cn/problems/word-break/description/

        给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。

        注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。

示例 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

理解：

     ① dp[i] : 字符串长度为 i 的话，dp[i] 为 true，表示可以拆分为 一个或多个 在字典中出现的单词。

     ② 如果确定 dp[j] 是 true，且 [j, i] 这个区间的子串出现在字典里，那么 dp[i] 一定是true。（ j < i ）。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j] 是 true) 那么 dp[i] = true。

     ③ dp[i] 的状态依靠 dp[j] 是否为 true，那么 dp[0] 就是递推的根基，dp[0] 一定要为true。

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(), wordDict.end());
        vector<bool> dp(s.size() + 1, false);
        dp[0] = true;
        for (int i = 1; i <= s.size(); i++) {    // 遍历背包
            for (int j = 0; j < i; j++) {   // 遍历物品
                string word = s.substr(j, i - j);   // 从 j 开始的 i-j 个字符
                if (wordSet.find(word) != wordSet.end() && dp[j]) {
                    dp[i] = true;
                }
            }
        }
        return dp[s.size()];
    }
};

三、总结

1. 01背包问题

2. 完全背包问题