完全背包
與01背包差別是物品可以重復(fù)用莉兰，那么在遍歷容量就要從小到大遍歷
// 先遍歷物品，再遍歷背包for(inti=0;i<weight.size();i++){// 遍歷物品for(intj=weight[i];j<=bagWeight;j++){// 遍歷背包容量dp[j]=max(dp[j],dp[j-weight[i]]+value[i]);}}
518.?零錢兌換?II?
動(dòng)規(guī)五步曲
確定dp數(shù)組以及下標(biāo)的含義
dp[j]：湊成總金額j的貨幣組合數(shù)為dp[j]
確定遞推公式
dp[j] += dp[j - coins[i]]
dp數(shù)組如何初始化
dp[0] = 1
確定遍歷順序
外層for循環(huán)遍歷物品（錢幣）庶橱，內(nèi)層for遍歷背包
intchange(intamount,vector<int>&coins){vector<int>dp(amount+1,0);dp[0]=1;for(inti=0;i<coins.size();i++){// 遍歷物品for(intj=coins[i];j<=amount;j++){// 遍歷背包dp[j]+=dp[j-coins[i]];}}returndp[amount];}
舉例推導(dǎo)dp數(shù)組
377.?組合總和?Ⅳ
動(dòng)規(guī)五部曲
確定dp數(shù)組以及下標(biāo)的含義
dp[i]: 湊成目標(biāo)正整數(shù)為i的排列個(gè)數(shù)為dp[i]
確定遞推公式
dp[i] += dp[i - nums[j]]
dp[0]=1
確定遍歷順序
個(gè)數(shù)可以不限使用贮勃，說明這是一個(gè)完全背包
得到的集合是排列，說明需要考慮元素之間的順序
外層for遍歷背包苏章，內(nèi)層for循環(huán)遍歷物品
計(jì)算dp[4]的時(shí)候，結(jié)果集只有 {1,3} 這樣的集合奏瞬，不會有{3,1}這樣的集合枫绅，因?yàn)閚ums遍歷放在外層，3只能出現(xiàn)在1后面
舉例來推導(dǎo)dp數(shù)組
intcombinationSum4(vector<int>&nums,inttarget){vector<int>dp(target+1,0);dp[0]=1;for(inti=0;i<=target;i++){// 遍歷背包for(intj=0;j<nums.size();j++){// 遍歷物品if(i-nums[j]>=0&&dp[i]<INT_MAX-dp[i-nums[j]]){dp[i]+=dp[i-nums[j]];}}}returndp[target];}
