Leetcode題解 Python & C#：六月挑戰DAY7 Coin Change 2

給各硬幣的幣值 coins，與目標金額 amount ，要找出有幾種硬幣組合的總金額會等於 amount。

在這題琢磨了好幾小時，因為對於 DP 速度感到好奇，這題用 DFS 就是慢。

對於這種求特定組合數的題目，最重要的就是去看限制條件，再決定 DP 要取什麼要比較快。

「0 <= amount <= 5000」這意味著每道題目的答案並不是大數目，從「the answer is guaranteed to fit into signed 32-bit integer」也可得知。

如果是天文數字，就會有 % (10**9+7) ，這樣的題型不可能遍歷所有位置去解。但這題最快的方法是去跑遍所有位置。

這題用 DFS 無法達到「收斂」的效果，收斂要把幾種可能答案做取捨並向上傳遞，用 DFS 只能開支散葉，也就不需要用遞迴函數。

用各硬幣累加，在總金額 0 的地方預設為 1 ，各幣從幣值處開始，dp[i] += dp[i-coin]，直到 i 超出 amount。

如 5, [1,2,5]，在 dp[2] == 2，到達此處的方法有 1*2, 2*1，或寫 1 + 1, 0 + 2。固定增加的方式，輪到幣值永遠加在已計路逕的最後方，也使得不會有重複出現。 

1: [1,1,1,1,1,1]

2: [1,1,2,2,3,3]

5: [1,1,2,2,3,4]

「1」：1+1+1+1+1 => dp[4] 

「2」：1+1+1+2 => dp[3]

「2」：1+2+2 => dp[3] => 1+2(dp[1]) + 2

「5」：5 => dp[0]

Python

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        dp  = [0] * (amount+1)
        dp[0] = 1
        for coin in coins: 
            for i in range(coin, amount+1):                
                dp[i] += dp[i - coin]
        return dp[-1]

C#

public class Solution {
    public int Change(int amount, int[] coins) {
        var dp = new int[amount+1];
        dp[0] = 1;
        foreach(int coin in coins)
        {
            for(int i = coin; i <= amount; i++)
            {
                dp[i] += dp[i - coin];
            }
        }
        return dp[amount];
    }
}