# 目标和
题目链接🔗
结果 target 可以将数组分为两部分，左组合 left - 右组合 right = target。
left + right = sum，而数组总和是固定的，因此 right = sum - left。
那么 left - (sum - left) = target，left = (target + sum) / 2。
target 和 sum 是固定值，那么问题就转化为在数组中求 left 的组合。
转化为背包问题就是，装满容量为 left 的背包，有几种方法。每个数只能取一次，就是 01 背包。
- 确认 dp 数组及下标含义
dp [j]: 填满容积为 j 的背包，有 dp [j] 种方法。
- 确定递推公式
如果取当前的 nums [i]，凑成 d [j] 就有 dp [j-nums [i]] 种方法。
递推公式为：$$dp [j] += dp [j - nums [i]]$$
- dp 数组如何初始化
dp [0] = 1，因为 dp [0] 是一切递推结果的开始。
dp [j] 其他下标对应的数值应该初始化为 0，从递推公式也可以看出，dp [j] 要保证是 0 的初始值，才能正确的由 dp [j - nums [i]] 推导出来。
- 确定遍历顺序
nums 为物品，left 为背包，先物品后背包。
- 举例推导 dp 数组
输入：nums: [1, 1, 1, 1, 1], S: 3
bagSize = (S + sum) / 2 = (3 + 5) / 2 = 4
class Solution { | |
public: | |
int findTargetSumWays(vector<int>& nums, int S) { | |
int sum = 0; | |
for (int i = 0; i < nums.size(); i++) sum += nums[i]; | |
if (abs(S) > sum) return 0; // 此时没有方案 | |
if ((S + sum) % 2 == 1) return 0; // 此时没有方案 | |
int bagSize = (S + sum) / 2; | |
vector<int> dp(bagSize + 1, 0); | |
dp[0] = 1; | |
for (int i = 0; i < nums.size(); i++) { | |
for (int j = bagSize; j >= nums[i]; j--) { | |
dp[j] += dp[j - nums[i]]; | |
} | |
} | |
return dp[bagSize]; | |
} | |
}; |
如果能找到目标和的话 S + sum 不可能为奇数，因为数组元素都是整数，要找的子集和也应该是整数。如果为奇数，那题解中的 bagSize 就是小数，这不可能。
# 一零和
题目链接🔗
本题种 strs 数组里的元素就是物品，每个物品都是一个。m、n 相当于是一个背包，有两个维度。
- 确定 dp 数组以及下标的含义
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] = max (dp [i][j], dp [i - zeroNum][j - oneNum] + 1)$$
- dp 数组如何初始化
因为物品价值不会是负数，初始为 0，保证递推的时候 dp [i][j] 不会被初始值覆盖。
- 确定遍历顺序
物品就是 strs 里的字符串，背包容量就是题目描述中的 m 和 n。
- 举例推导 dp 数组
以输入：["10","0001","111001","1","0"]，m = 3，n = 3 为例：
class Solution { | |
public: | |
int findMaxForm(vector<string>& strs, int m, int n) { | |
vector<vector<int>> dp(m + 1, vector<int> (n + 1, 0)); // 默认初始化 0 | |
for (string str : strs) { // 遍历物品 | |
int oneNum = 0, zeroNum = 0; | |
for (char c : str) { | |
if (c == '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], dp[i - zeroNum][j - oneNum] + 1); | |
} | |
} | |
} | |
return dp[m][n]; | |
} | |
}; |
# 完全背包理论基础
完全背包模板题：有 n 件物品和一个最多能背重量为 w 的背包。第 i 件物品的重量是 weight [i]，得到的价值是 value [i] 。每件物品有无限多哥，求解将哪些物品装入背包里物品价值总和最大。
背包最大重量为 4，物品为：
| 重量 | 价值 | |
|---|---|---|
| 物品 0 | 1 | 15 |
| 物品 1 | 3 | 20 |
| 物品 2 | 4 | 30 |
思路和 01 背包一致，但由于完全背包的物品是可以添加多次的，所以小从小到大遍历背包容量。遍历顺序先物品还是先背包都可以。
void CompletePack() { | |
vector<int> weight = {1, 3, 4}; | |
vector<int> value = {15, 20, 30}; | |
int bagWeight = 4; | |
vector<int> dp(bagWeight + 1, 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]); | |
} | |
} | |
cout << dp[bagWeight] << endl; | |
} |
# 零钱兑换 II
题目链接🔗
典型的完全背包问题。
- 确定 dp 数组以及下标的含义
dp [j]: 凑成总金额 j 的货币组合数为 dp [j]。
- 确定递推公式
dp [j] 是所有 dp [j - coins [i]] 相加。
所以递推公式为：$$dp [j] += dp [j-coins [i]]$$
- dp 数组如何初始化
首先 dp [0] 一定要为 1，dp [0] = 1 是递推公式的基础。dp [0]=1 还说明了一种情况：如果正好选了 coins [i] 后，也就是 j-coins [i] == 0 的情况表示这个硬币刚好能选，此时 dp [0] 为 1 表示只选 coins [i] 存在这样的一种选法。
下标非 0 的 dp [j] 初始化为 0，这样累计加 dp [j - coins [i]] 的时候才不会影响真正的 dp [j]
- 确定遍历顺序
本题要求的是硬币的组合数，不是排列数。for 循环的先后顺序有说法。
先遍历物品在遍历背包求出的事组合数，而先遍历背包再遍历物品求出的是排列数。
- 举例推导 dp 数组
输入: amount = 5, coins = [1, 2, 5] ，dp 状态图如下：
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++) { // 遍历背包 | |
dp[j] += dp[j - coins[i]]; | |
} | |
} | |
return dp[amount]; | |
} | |
}; |
