LeetCode518. 零钱兑换II
题目链接：518. 零钱兑换II
独上高楼，望尽天涯路
组合问题和完全背包的混合应用，感觉脑中模拟的不是很清晰，但是靠着背包问题的代码技巧和模板就能比较容易的ac，玄学起来了。
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 + 1; j++) {
dp[j] += dp[j - coins[i]];
}
}
return dp[amount];
}
};
慕然回首，灯火阑珊处
在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
已经开始有点懵了QAQ。
LeetCode377. 组合总和IV
题目链接：377. 组合总和IV
独上高楼，望尽天涯路
在求装满背包有几种方案的时候，认清遍历顺序是非常关键的。
如果求组合数就是外层for循环遍历物品，内层for遍历背包。
如果求排列数就是外层for遍历背包，内层for循环遍历物品。
经过上一道题对于排列问题的提醒，这道题也很快就ac了，但是对于其内在原理的理解还比较浅，最近需要赶进度，第一遍先记住代码写法，希望第二遍能够加深对于本质的理解。
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target + 1, 0);
dp[0] = 1;
for(int j = 0; j < target + 1; j++) {
for (int i = 0; i < nums.size(); i++) {
if (j - nums[i] >= 0 && dp[j] < INT_MAX - dp[j - nums[i]]) { // 防止两个int相加溢出
dp[j] += dp[j - nums[i]];
}
}
}
return dp[target];
}
};
慕然回首，灯火阑珊处
总结一下，这是一道排列问题+完全背包问题。
- 确定dp数组以及下标的含义
dp数组表示的是目标整数为j时的排列个数。
- 确定递推公式
排列组合问题经典的递推公式，dp[j] += dp[j - nums[i]]。
- dp数组如何初始化
对于排列组合问题，初始化一般为dp[0] = 1，这很重要！
- 确定遍历顺序
对于排列问题，与组合问题正相反，应该外层遍历背包容量，内层遍历物品。同时这是一个完全背包问题，所以我们正向遍历背包容量。
- 返回值
返回dp[target]即可。