Leetcode 518. 零钱兑换 II 动态规划

原题链接：Leetcode 518. 零钱兑换 II

可参考官解：零钱兑换 II 和这个解答：[Java/Python3/C++]动态规划：拆分零钱兑换子问题（嵌套循环的秘密）【图解】

此题需要仔细想象和Leetcode 377. 组合总和 Ⅳ 动态规划的区别，本次是求组合数，是不考虑顺序的，Leetcode 377. 组合总和 Ⅳ 动态规划是求排列数，需要考虑顺序，因此答案更大。

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1,0); // dp[i]表示凑成金额i的组合数，初始都为0表示不可凑dp[0] = 1;         // 金额0有一种组合方式，由0枚硬币组成vector<int> can_change(amount + 1, 0);can_change[0] = 1;for (auto& c : coins) {// 枚举每一个金额for (int a = c; a <= amount; a++) {can_change[a] |= can_change[a - c];}}if (can_change[amount] == 0)return 0;// 枚举每一种硬币// 先遍历所有硬币，再遍历金额数，这样会考虑使用硬币的顺序，不会出现先选1,再选2，和先选2再选1同时出现的情况// 比如amount = 5, coins = [1, 2,// 5]，第一次外循环和内循环，就是计算，所有金额数只用coin=1组合得到的情况// 第二次外循环和内循环，遍历在之前的金额数dp[i]的基础上，加上2得到当前金额数的可能，即先1后2的可能，不会再反复计算先2后1的可能for (auto coin : coins) {for (int i = coin; i <= amount; i++) {dp[i] += dp[i - coin];}}return dp[amount];}
};// 5
// [1,2,5]
// 1
// dp[1]=0+dp[0]=1;
// dp[2]=0+dp[1]=1;
// dp[3]=0+dp[2]=1;
// dp[4]=0+dp[3]=1;
// dp[5]=0+dp[4]=1;// 2
// dp[2]=1+dp[0]=2;
// dp[3]=1+dp[1]=2;
// dp[4]=1+dp[2]=3;
// dp[5]=1+dp[3]=3;// 5
// dp[5]=3+dp[0]=4;