# 【LeetCode】 518. Coin Change 2

## Description
> You are given coins of different denominations and a total amount of money. Write a function to compute the number of combinations that make up that amount. You may assume that you have infinite number of each kind of coin.

> Note:
> You can assume that
> * 0 <= amount <= 5000
> * 1 <= coin <= 5000
> * the number of coins is less than 500
> * the answer is guaranteed to fit into signed 32-bit integer

> 給予你不同面額的金幣和一個金額的總數。寫一個函式去計算有幾種組合可以湊成該金額。你可以假設每種面額的金幣都有無限枚。

> 提示：
> 你可以假設
> * 0 <= amount <= 5000
> * 1 <= coin <= 5000
> * 金幣的種類數少於 500
> * 答案保證可以用 32 位元的有號正整數去表示

## Example:

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

## Solution

* 一開始想到的是貪婪法，概念是一直拿硬幣，如果剛好拿滿就讓答案加一；拿超過就換下一種硬幣。

class Solution {
public:
    void greedy(int amount, vector<int> coins, int& ans)
    {
        if(amount == 0) ans++;
        if(coins.empty()) return;
        else if(amount > 0)
        {
            greedy(amount - coins.front(), coins, ans);
            coins.erase(coins.begin());
            greedy(amount, coins, ans);
        }
    }
    int change(int amount, vector<int>& coins) {
        int ans = 0;
        greedy(amount, coins, ans);
        return ans;
    }
};

* 結果吃了TLE，當金錢總數越大時這個演算法會跑超級久(基本上每一種組合都拿過一次，太過耗時)。
---
* 接著想到使用DP來加速。
* 總共產生`0 ~ amount`共`amount + 1`個格子，其代表金額為`i`的時候有的組合數。
* 因此答案就是`DP[amount]`。
* 初始設定`DP[0] = 1`。(每種硬幣都不拿、一種組合)。
* 接著跑每一種硬幣，去更新 DP 即可。

### Code

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

###### tags: `LeetCode` `C++`