原題鏈接：Leetcode 518. 零錢兌換 II

可參考官解：零錢兌換 II 和這個解答：[Java/Python3/C++]動態(tài)規(guī)劃：拆分零錢兌換子問題（嵌套循環(huán)的秘密）【圖解】

此題需要仔細想象和Leetcode 377. 組合總和 Ⅳ 動態(tài)規(guī)劃的區(qū)別，本次是求組合數(shù)，是不考慮順序的，Leetcode 377. 組合總和 Ⅳ 動態(tài)規(guī)劃是求排列數(shù)，需要考慮順序，因此答案更大。

class Solution {
public:int change(int amount, vector<int>& coins) {vector<int> dp(amount + 1,0); // dp[i]表示湊成金額i的組合數(shù)，初始都為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;// 枚舉每一種硬幣// 先遍歷所有硬幣，再遍歷金額數(shù)，這樣會考慮使用硬幣的順序，不會出現(xiàn)先選1,再選2，和先選2再選1同時出現(xiàn)的情況// 比如amount = 5, coins = [1, 2,// 5]，第一次外循環(huán)和內(nèi)循環(huán)，就是計算，所有金額數(shù)只用coin=1組合得到的情況// 第二次外循環(huán)和內(nèi)循環(huán)，遍歷在之前的金額數(shù)dp[i]的基礎上，加上2得到當前金額數(shù)的可能，即先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;