6. 一和零（LeetCode-474）
题目
给你一个二进制字符串数组 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
思路
五部曲
dp[i][j] 含义
最多能装 i 个 0 和 j 个 1 的背包的最大子集的数量
递推公式
虽然是二维的，但其实只包含背包重量这一个方面，本质还是滚动数组。
d p [ i ] [ j ] = m a x ( d p [ i ] [ j ] , d p [ i − n u m Z e r o ] [ j − n u m O n e ] + 1 )
其中，n u m Z e r o 和 n u m O n e分别表示当前物品，即当前子集的零和一个数。相当于物品的重量。而后面的加一相当于物品的价值。为什么是一？因为加上当前物品后，最大子集数量就加一了。
数组初始化
物品价值不为负数，所以初始化为零即可
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要倒序
测试用例
本图为最后状态
代码展示
class Solution { public: int findMaxForm(vector<string> &strs, int m, int n) { vector<vector<int>> dp(m + 1, vector<int>(n + 1)); for (int idx = 0; idx < strs.size(); idx++) { int numZero = 0, numOne = 0; for (char val : strs[idx]) { if (val == '0') { numZero++; } else { numOne++; } } for (int i = m; i >= numZero; i--) { for (int j = n; j >= numOne; j--) { dp[i][j] = max(dp[i][j], dp[i - numZero][j - numOne] + 1); } } } return dp[m][n]; } };
完全背包
1. 例题
题目
有N件物品和一个最多能背重量为 W WW 的背包。第 i ii 件物品的重量是w e i g h t [ i ] weight[i]weight[i],得到的价值是 v a l u e [ i ] value[i]value[i]。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。同样leetcode上没有纯完全背包问题，都是需要完全背包的各种应用，需要转化成完全背包问题，所以我这里还是以纯完全背包问题进行讲解理论和原理。
在下面的讲解中，我依然举这个例子：
背包最大重量为4.
物品为：
| 重量 | 价值 | |
| 物品0 | 1 |
15 |
| 物品1 | 3 |
20 |
| 物品2 | 4 |
30 |
每件商品都有无限个
问：背包能背的物品最大价值是多少？
思路
01背包和完全背包唯一不同在于遍历顺序上
01背包核心代码
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]); } }
01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次
举例：
假设物品0重量 w e i g h t [ 0 ] = 1，价值 v a l u e [ 0 ] = 15
如果是正序遍历
d p [ 1 ] = d p [ 1 − w e i g h t [ 0 ] ] + v a l u e [ 0 ] = 15
d p [ 2 ] = d p [ 2 − w e i g h t [ 0 ] ] + v a l u e [ 0 ] = 30
在第一行运行后 d p [ 1 ] 的状态已经发生改变，意味着已经放了物品0，而第二行运行后，叠加了改变后的 d p [ 1 ] ，意味着物品0被放了两次。
那么为什么之前在写二维数组的时候是正序的？
因为我们实际求的是上一行的状态，也就是不放当前物品的情况，只不过在滚动数组中，压缩了状态。也即当前元素的公式被运行后，当前元素的状态（在当前行，包括物品0）覆盖了先前状态（在上一行，不含物品0），所以一维中倒序是为了保证物品只被放入一次！
而完全背包的物品是可以添加多次的，所以要从小到大去遍历
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]); } }
遍历顺序是否强制先遍历物品，再遍历背包容量？
在01背包的一维数组中必须先遍历物品，再遍历背包容量。
而在完全背包的一维数组中，循环嵌套顺序却无所谓。
因为 dp[j] 是根据它同行的左边的元素推出来的，而无论哪种顺序，它的左值都是更新过的，可用的。
但先后顺序可以颠倒的前提是纯完全背包问题！题目变化的可能就不行
代码展示
#include <iostream> #include <cmath> #include <vector> using namespace std; void test_CompletePack() { vector<int> weight = {1, 3, 4}; vector<int> value = {15, 20, 30}; int bagWeight = 4; vector<int> dp(bagWeight + 1); 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]); } } cout << dp[bagWeight]; } int main() { test_CompletePack(); return 0; }
2. 零钱兑换Ⅱ（LeetCode-518）
题目
给你一个整数数组 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
提示：
1 <= coins.length <= 300
1 <= coins[i] <= 5000
coins 中的所有值 互不相同
0 <= amount <= 5000
思路
本题要点：
硬币有无限个，所以完全背包问题
本题要求凑成总金额的个数
五部曲
dp[j] 含义
凑成总金额为 j 的硬币组合数（背包的容量为 j 的背包恰好装满的方法数）
递推公式
d p [ j ] = d p [ j ] + d p [ j − c o i n s [ i ] ]
数组初始化
dp[0]=1 从数组含义看：凑成总金额为零的硬币组合数为一
遍历顺序
先遍历物品，嵌套遍历背包，且背包遍历要正序
本题不是纯完全背包问题，不能交换顺序。因为本题求的是组合数，要求元素之间没有顺序。
测试用例
代码展示
class Solution { public: int change(int amount, vector<int> &coins) { vector<int> dp(amount + 1); dp[0] = 1; for (int i = 0; i < coins.size(); i++) { for (int j = coins[i]; j <= amount; j++) { dp[j] += dp[j - coins[i]]; } } return dp[amount]; } };
3. 组合总和Ⅳ（LeetCode-377）
题目
给你一个由 不同 整数组成的数组 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
提示：
1 <= nums.length <= 200
1 <= nums[i] <= 1000
nums 中的所有元素 互不相同
1 <= target <= 1000
**进阶：**如果给定的数组中含有负数会发生什么？问题会产生何种变化？如果允许负数出现，需要向题目中添加哪些限制条件？
思路
由示例一最后一行得，题目看似求的组合数，实际上求的是排序数
五部曲
dp[j] 含义
凑成目标正整数为 j jj 的排列个数（使背包容量为 j jj 的背包恰好装满的组合数——不同排序算做不同组合）
递推公式
d p [ j ] + = d p [ j − d p [ n u m s ] ]
数组初始化
dp[0]=1
遍历顺序
先遍历背包，嵌套遍历物品，且物品遍历要正序
如果把遍历 nums（物品）放在外循环，遍历target的作为内循环的话，举⼀个例子：计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有 {3,1} 这样的集合，因为nums遍历放在外层，3只能出现在1后面
代码展示
class Solution { public: int combinationSum4(vector<int> &nums, int target) { vector<int> dp(target + 1); dp[0] = 1; for (int j = 0; j <= target; j++) { for (int i = 0; i < nums.size(); i++) { if (j >= nums[i] && dp[j] < INT_MAX - dp[j - nums[i]]) { dp[j] += dp[j - nums[i]]; } } } return dp[target]; } };
4. 爬楼梯（改写成完全背包）
题目
原题为LeetCode-70，是一道简单动态规划，现改写为：
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。 每次你可以爬 m mm 个台阶。你有多少种不同的方法可以爬到楼顶呢
思路
一步爬一个或两个或三个或 m mm 个就是物品，楼顶就是背包，其实就是问装满背包的方法有多少种。再想这是排序数还是组合数？明显先2后1（先爬2阶楼梯再爬1阶楼梯）和先1后2是不同的方法，所以求的是排序数，那么就要求先遍历背包，嵌套遍历物品
五部曲
dp[j] 含义
爬到有 j jj 个台阶的楼顶的方法数
递推公式
d p [ j ] + = d p [ j − i ]
数组初始化
dp[0]=1
遍历顺序
上文已说明
代码实现
class Solution { public: int climbStairs(int n, int m) { vector<int> dp(n + 1, 0); dp[0] = 1; for (int i = 1; i <= n; i++) { // 遍历背包 for (int j = 1; j <= m; j++) { // 遍历物品 if (i - j >= 0) dp[i] += dp[i - j]; } } return dp[n]; } };
代码中m表示最多可以爬m个台阶，代码中把m改成2就是本题70.爬楼梯可以AC的代码了
5. 零钱兑换（LeetCode-322）
题目
给你一个整数数组 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
提示：
1 <= coins.length <= 12
1 <= coins[i] <= 231 - 1
0 <= amount <= 104
思路
五部曲
dp[j] 含义
凑成总金额为 j jj 所需的最少硬币数
递推公式
求最少硬币数，一种就是不含当前物品（这里说的当前物品就是指当前的这枚硬币，假如当前硬币值为2，不是说背包里就不含硬币值为2的硬币了，因为是硬币无限枚，所以很可能有，而是说不含当前这枚硬币值为2的硬币）的硬币数，数值保持不变。另一种是含当前物品的硬币数，数值要加一（加上当前物品）
d p [ j ] = m i n ( d p [ j ] , d p [ j − c o i n s [ i ] ] + 1 )
数组初始化
凑成总金额为2的硬币数肯定为零，而其他要初始化为最大值，不然在运行递推公式时初始值会覆盖 d p [ j − c o i n s [ i ] ] + 1
遍历顺序
这里求最少硬币数量，硬币是组合数还是排列数都无所谓，所以顺序随意
代码实现
class Solution { public: int coinChange(vector<int> &coins, int amount) { vector<int> dp(amount + 1, INT_MAX); dp[0] = 0; for (int i = 0; i < coins.size(); i++) { for (int j = coins[i]; j <= amount; j++) { // 如果dp[j - coins[i]]是初始值则跳过 if (dp[j - coins[i]] != INT_MAX) { dp[j] = min(dp[j], dp[j - coins[i]] + 1); } } } return dp[amount] == INT_MAX ? -1 : dp[amount]; } };
易错点在 d p [ j − c o i n s [ i ] ]是初始值没有跳过，还有记得没有任何一种硬币组合能组成总金额，返回 -1
