背包問題總結(jié)
知識(shí)要點(diǎn)1
- 如果求組合數(shù)就是外層for循環(huán)遍歷物品，內(nèi)層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];
- 如果求排列數(shù)就是外層for遍歷背包啼肩，內(nèi)層for循環(huán)遍歷物品
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];
知識(shí)要點(diǎn)2
- 01背包內(nèi)層循環(huán)從大到小
- 完全背包內(nèi)層循環(huán)從小到大
知識(shí)要點(diǎn)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)
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
