完全背包的理論基礎(chǔ)：
因?yàn)橐粋€(gè)物品可以取多次梢薪，因此遍歷順序和0-1背包不同。
0-1背包遍歷背包的時(shí)候是倒序尝哆，這里是順序秉撇，允許重復(fù)，且物品和背包可以交換遍歷順序秋泄。
完全背包先遍歷物品琐馆，再遍歷背包是組合問題，物品中沒有重復(fù)
先遍歷背包印衔，再遍歷物品時(shí)排列問題啡捶，物品中會(huì)有重復(fù)，比如1奸焙，2和2,1
算法思想：
一個(gè)物品可以使用多次，求裝滿這個(gè)背包有多少次。完全背包問題与帆。
遞推公式有點(diǎn)類似于爬樓梯了赌，最后一步可以有1-n步的情況，因此遞推公式為:
dp[j]= 求和 dp[j-coins[i]]
代碼：
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];
? ? }
};
算法思想：
完全背包中的排列問題玄糟，先遍歷背包勿她，再遍歷物品≌篝幔可以類比于爬樓梯逢并，爬樓梯是個(gè)排列問題
代碼：
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;j++)
? ? ? ? {
? ? ? ? ? ? for(int i=0;i<nums.size();i++)
? ? ? ? ? ? {
? ? ? ? ? ? ? ? if(j-nums[i]>=0 && dp[j] < INT_MAX - dp[j-nums[i]])
? ? ? ? ? ? ? ? ? ? dp[j] += dp[j-nums[i]];
? ? ? ? ? ? }
? ? ? ? }
? ? ? ? return dp[target];
? ? }
};
