背包问题总结
知识要点1
- 如果求组合数就是外层for循环遍历物品，内层for遍历背包
vector<int> dp(target+1, 0);
dp[0] = 1;
for (int i=0; i<nums.size(); ++i) {
for (int j=nums[i]; j<=target; ++j) {
dp[j] += dp[j-nums[i]];
}
}
return dp[target];
- 如果求排列数就是外层for遍历背包，内层for循环遍历物品
vector<int> dp(target+1, 0);
dp[0] = 1;
for (int j=1; j<=target; ++j) {
for (int i=0; i<nums.size(); ++i) {
if (j >= nums[i]) dp[j] += dp[j-nums[i]];
}
}
return dp[target];
知识要点2
- 01背包内层循环从大到小
- 完全背包内层循环从小到大
知识要点3
- 组合问题公式：dp[i] += dp[i-num]
- True、False问题公式：dp[i] = dp[i] or dp[i-num]
- 最大最小问题公式：dp[i] = min(dp[i], dp[i-num]+1) 或者 dp[i] = max(dp[i], dp[i-num]+1)
