完全背包
与01背包差别是物品可以重复用，那么在遍历容量就要从小到大遍历
// 先遍历物品，再遍历背包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
动规五步曲
确定dp数组以及下标的含义
dp[j]：凑成总金额j的货币组合数为dp[j]
确定递推公式
dp[j] += dp[j - coins[i]]
dp数组如何初始化
dp[0] = 1
确定遍历顺序
外层for循环遍历物品（钱币），内层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];}
举例推导dp数组
377. 组合总和 Ⅳ
动规五部曲
确定dp数组以及下标的含义
dp[i]: 凑成目标正整数为i的排列个数为dp[i]
确定递推公式
dp[i] += dp[i - nums[j]]
dp[0]=1
确定遍历顺序
个数可以不限使用，说明这是一个完全背包
得到的集合是排列，说明需要考虑元素之间的顺序
外层for遍历背包，内层for循环遍历物品
计算dp[4]的时候，结果集只有 {1,3} 这样的集合，不会有{3,1}这样的集合，因为nums遍历放在外层，3只能出现在1后面
举例来推导dp数组
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];}
