518. 零钱兑换 II

与0-1背包里目标和那道题形成联动，求得是组合数

链接：代码随想录

 

1、组合数：外层for循环遍历物品（钱币），内层for遍历背包（金钱总额）的情况：

因为每一行，比如第一行只放了物品1，物品2等到第二行才放。则当遍历dp[2]只会有（1，2），不会出现（2，1）.

for (int i = 0; i < coins.size(); i++) { // 遍历物品for (int j = coins[i]; j <= amount; j++) { // 遍历背包容量dp[j] += dp[j - coins[i]];}
}

2、排列数：外层for循环遍历背包（金钱总额），内层for遍历物品的情况：

背包容量的每一个值，都是经过 1 和 5 的计算，包含了{1, 5} 和 {5, 1}两种情况。

for (int j = 0; j <= amount; j++) { // 遍历背包容量for (int i = 0; i < coins.size(); i++) { // 遍历物品if (j - coins[i] >= 0) dp[j] += dp[j - coins[i]];}
}

解法：本题是组合数，所以先背包

 

class Solution {
/*假设每一种面额的硬币有无限个。一看就是完全背包
dp[i][j] 代表只用0---i前i个硬币，且凑的总金额是j的硬币组合种数
因为问的不是最大价值，只是种类数d[i][j]+=dp[i-1][j-coins[i]];
*/
public:int change(int amount, vector<int>& coins) {int n=coins.size();vector<int>dp(amount+1,0);//初始化必须为1，不然之后推导的都是0dp[0]=1;//vector<vector<int>>dp(n,vector<int>(amount+1,0));for(int i=0;i<n;i++){for(int j=coins[i];j<=amount;j++){dp[j]+=dp[j-coins[i]];}}return dp[amount];}
};

 377. 组合总和 Ⅳ

链接：代码随想录

 

 本题与前面的形成对比，是排列数。

先遍历背包容量，再遍历物品

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