# 322-Coin Change
###### tags: `Medium`
## Question
https://leetcode.com/problems/coin-change/
## Key
1. DP

因為目的是找到符合條件之總和所需的最小金幣數量，不只要記住前一次的結果，而是要記住前面全部的結果，因為沒有辦法知道會有什麼幣值，所以只能全部記住，故用動態規劃來解決此問題。

解題之前 先定義動態規劃的狀態和觀察狀態間的關聯性:dp[amount] 代表金幣加總為 amount 時所需要的最小金幣數，目標總和 amount 以下之可能發生的子總和 amount 完全是取決於金幣的種類而定

假設我取了一个值為5的硬幣，由於目標值是 11，所以如果能知道 dp[6]，那麼就知道组成dp[11]的值了，因此更新 dp[i] 的方法就是遍歷每个硬幣，如果遍歷到的硬幣值小於i值（比如不能用值为5的硬幣去更新 dp[3]）时，用 dp[i - coins[j]] + 1 来更新 dp[i]，所以狀態轉移方程為：

>dp[i] = min(dp[i], dp[i - coins[j]] + 1);

換句話說，dp[i - coins[j]] + 1是為了檢查過去一回合j種硬幣2疊加完的最小值，即是否出現更大的幣種。

原先已經初始化每種amount下需要的硬幣數為amount+1，所以湊不出來amount的時候，必定大於amount，就回傳-1。

時間複雜度為 O( amount 大小 * coins 長度)
空間複雜度為 O( amount 大小)

## Reference
## DP Solution

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int dp[amount + 1]; 
        dp[0] = 0; 
        
        for (int i = 1; i <= amount; i++)//最小要從1元開始
        {
            int min = 10001; 
            for (int coin: coins)// 計算每一種幣值
            {
                if (i >= coin && min > (dp[i-coin] + 1)) //dp[i - coin]就是表示i-coin那個數值最少能用多少硬幣組成
                {
                    min = dp[i - coin] + 1; //加一個硬幣
                }
            }
            dp[i] = min; //更新硬幣數
        }
        
        return dp[amount] == 10001 ? -1 : dp[amount]; 
    }
};

- Neat version

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i <= amount; ++i) {
            for (int j = 0; j < coins.size(); ++j) {
                if (coins[j] <= i) {
                    dp[i] = min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return (dp[amount] > amount) ? -1 : dp[amount];
    }
};