广州制作软件seo公司上海

目录

一、理论基础

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. 完全背包问题