###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++`

# 518. Coin Change II

## [題目連結:] https://leetcode.com/problems/coin-change-ii/description/

## 題目:
You are given an integer array ```coins``` representing coins of different denominations and an integer ```amount``` representing a total amount of money.

Return the number of combinations that make up that amount. If that amount of money cannot be made up by any combination of the coins, return ```0```.

You may assume that you have an infinite number of each kind of coin.

The answer is **guaranteed** to fit into a signed **32-bit** integer.

**Example 1:**

Input: amount = 5, coins = [1,2,5]
Output: 4
Explanation: there are four ways to make up the amount:
5=5
5=2+2+1
5=2+1+1+1
5=1+1+1+1+1

**Example 2:**

Input: amount = 3, coins = [2]
Output: 0
Explanation: the amount of 3 cannot be made up just with coins of 2.

**Example 3:**

Input: amount = 10, coins = [10]
Output: 1

## 解題想法:
* 此題為給定不同面額的錢幣與一個總金額，假設每一種面額的錢幣有無限個
* 求出可湊成總金額的組合數
* 使用DP:
* 定義**dp[i]: 金額為i的組合數**
* 初始:
* dp[0]=1
* 0元: 完全不拿1種選擇
* 本題關鍵:
* **第一圈迴圈: 錢幣的種類**
* 第二圈迴圈:
* 調整dp[i]
* 動態方程式:
* **dp[i]+=dp[i-value]** (for value in coins)
* 說明:
* 前 i 種硬幣湊出 amount 元的方法 = 前 i - 1 種硬幣湊出 amount 元的方法 + 前 i 種硬幣湊出 amount - value 元的方法
* 其中 value 為第 i 種硬幣的面額。
* trace如下:

        ex:
        amount  0   1   2   3   4   5
        coin:
            1   1   1   1   1   1   1
        (1)+2   1   1   2   2   3   3
        (12)5   1   1   2   2   3   4

* 說明可能有點籠統: 詳細可參考大神[https://vrabe.tw/blog/leetcode-518-coin-change-2

## Python:

class Solution(object):
    def change(self, amount, coins):
        """
        :type amount: int
        :type coins: List[int]
        :rtype: int
        """
        #dp[i]:金額為i的組合數
        dp=[0]*(amount+1)
        dp[0]=1 #0元 都不拿1種選擇
        for value in coins: #錢的種類
            #從value開始往後 
            #因為若當前i比value小 直接繼承之前的dp[i]就好 不用更動
            for i in range(value,amount+1):
                dp[i]+=dp[i-value]
        return dp[amount]

result=Solution()
amount = 5
coins = [1,2,5]
ans=result.change(amount,coins)
print(ans)

## C++:

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<int> dp(amount+1, 0);
        dp[0]=1;
        for (int value: coins){
            for (int i=value; i<amount+1; ++i){
                dp[i]+=dp[i-value];
            }
        }
        return dp[amount]; 
    }
};