LeetCode_518_零錢兌換 II

題目描述：

給定不同面額的硬币和一個總金額。寫出函數來計算可以湊成總金額的硬币組合數。假設每一種面額的硬币有無限個。 
示例 1:

輸入: amount = 5, coins = [1, 2, 5]
輸出: 4
解釋: 有四種方式可以湊成總金額:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1
示例 2:

輸入: amount = 3, coins = [2]
輸出: 0
解釋: 隻用面額2的硬币不能湊成總金額3。
示例 3:

輸入: amount = 10, coins = [10] 
輸出: 1
 

注意:

你可以假設：

0 <= amount (總金額) <= 5000
1 <= coin (硬币面額) <= 5000
硬币種類不超過 500 種
結果符合 32 位符号整數      

思路1：建立一個森林，此森林中子節點的權值不能小于父節點的權值，這樣可以避免重複計算的情況，遞歸的寫法雖然沒有問題，但是會發生逾時

class Solution {
public:
    void DFS(vector<int>& coins,int amount,int &num,int &pre){
        if(amount<=0)
            return ;
        for(int coin:coins){
            if(coin>amount)
                continue;
            if(coin==amount&&coin>=pre){
                num++;
                pre=coin;
            }
            if(coin>=pre)
                DFS(coins,amount-coin,num,pre);
        }
    }
    
    int change(int amount, vector<int>& coins) {
        int num=0;
        sort(coins.begin(),coins.end());//按照非遞減排序
        int pre=coins[0];
        DFS(coins,amount,num,pre);
        return num;
    }
};      

思路2：動态規劃

狀态轉移方程

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1);//vector 可以改變長度，沒有限制，int dp[amount+1]就超過限制
        dp[0]=1;
        for(int i=0;i<coins.size();i++){
            for(int j=1;j<=amount;j++){
                if(j>=coins[i])
                    dp[j]+=dp[j-coins[i]];
            }
        }
        return dp[amount];
    }
};