1. 完全背包理论基础
代码随想录：原文
1.1 完全背包
有N件物品和一个最多能背重量为W的背包。第i件物品的重量是weight[i]，得到的价值是value[i] 。每件物品都有无限个（也就是可以放入背包多次），求解将哪些物品装入背包里物品价值总和最大。
完全背包和01背包问题唯一不同的地方就是，每种物品有无限件。
- 01背包内嵌的循环是从大到小遍历，为了保证每个物品仅被添加一次
- 而完全背包的物品是可以添加多次的，所以要从小到大去遍历
// 先遍历物品，再遍历背包
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]);
}
}
- 在完全背包中，对于一维dp数组来说，其实两个for循环嵌套顺序是无所谓的
1.2 测试代码
// 先遍历物品，在遍历背包
void test_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;
}
int main() {
test_CompletePack();
}
2. 零钱兑换
代码随想录 : 原文
力扣题目：518.零钱兑换II
2.1 思路
纯完全背包是凑成背包最大价值是多少，而本题是要求凑成总金额的物品组合个数
组合不强调元素之间的顺序，排列强调元素之间的顺序
动规五步曲
- 确定dp数组以及下标的含义
- dp[j]：凑成总金额j的货币组合数为dp[j]
- 确定递推公式
- 递推公式：
dp[j] += dp[j - coins[i]];
- dp数组初始化
- dp[0] = 1是 递归公式的基础。如果dp[0] = 0 的话，后面所有推导出来的值都是0了。
- 下标非0的dp[j]初始化为0，这样累计加dp[j - coins[i]]的时候才不会影响真正的dp[j]
- 确定遍历顺序
- 本题要求凑成总和的组合数，元素之间明确要求没有顺序
- 外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）,这种遍历顺序中dp[j]里计算的是组合数
- 外层for循环遍历背包（金钱总额），内层for遍历物品（钱币）,这种遍历顺序中dp[j]里计算的是排列数
- 举例推导dp数组
2.2 代码实现
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];
}
};
- 时间复杂度: O(mn)，其中 m 是amount，n 是 coins 的长度
- 空间复杂度: O(m)
3. 组合总和
代码随想录 : 原文
力扣题目：377. 组合总和 Ⅳ
3.1 思路
本题题目描述说是求组合，但又说是可以元素相同顺序不同的组合算两个组合，其实就是求排列
动规五部曲
- 确定dp数组以及下标的含义
- dp[i]: 凑成目标正整数为i的排列个数为dp[i]
- 确定递推公式
求装满背包有几种方法，递推公式一般都是dp[i] += dp[i - nums[j]];
- dp数组初始化
dp[0] = 1 , 非0下标的dp[i]初始为0
- 确定遍历顺序
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包。
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品。
- 本题遍历顺序最终遍历顺序：target（背包）放在外循环，将nums（物品）放在内循环，内循环从前到后遍历。
- 打印dp数组
代码实现
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];
}
};
- 时间复杂度: O(target * n)，其中 n 为 nums 的长度
- 空间复杂度: O(target)
评论区