代码随想录算法训练营第四十四天|完全背包、518. 零钱兑换 I

完全背包

与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];}