題目：
給定幾種不同面額的硬幣，硬幣數量不限，要求用最少的硬幣數量湊出一個指定的金額 amount。如果無法湊出這個金額，則回傳 -1。

範例：

輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1

輸入: coins = [2], amount = 3
輸出: -1

解題思路

直覺使用貪心法，最少的硬幣個數的話，那麼先挑大硬幣，不足的話在尋找有沒有次等的硬幣能夠丟出來，全部都沒有的話就是 return -1。

但是遇到硬幣 [1, 5, 11]，並且要湊出金額 15 的話，就會得出 11x4枚+4x1枚=5枚 的結果，但最少硬幣數是 5x3枚，所以貪心法無法算出最優解。這題不能使用貪心法。

如果用動態規劃來解決的話，來試著分析看看，
假設我們有硬幣 [1, 2, 5]，並且要湊出金額 11，湊出金額 11，會面臨 3 種選擇情況，
情況1: 選取面額 1 的硬幣時，將面臨湊出 10 的情況。(硬幣數為1枚+Amount 金額為 10 的最少硬幣數)
情況2: 選取面額 2 的硬幣時，將面臨湊出 9 的情況。(硬幣數為1枚+Amount 金額為 9 的最少硬幣數)
情況3: 選取面額 5 的硬幣時，將面臨湊出 6 的情況。(硬幣數為1枚+Amount 金額為 6 的最少硬幣數)

我們從金額 0 開始，一步步從小金額推導出來，直到達到金額 11，dp[i] 為 Amount 金額下所需的最少硬幣數，未使用的硬幣以 X 表示。
每回合計算該金額中這三種情況的最小值，即該金額的最少硬幣數，

計算過程中，可發現每一個硬幣計算可以從上回合的狀態傳移過來，例如 Amount 金額 為 11 選取 Coin 5 時，剩下要湊出 6，dp[6] 為 Amount 金額為 6 的最少硬幣數，所以計算出硬幣數為 1+dp[6]=3枚，

因為每回合要取三種情況結果最小值，所以X的部份會用無限大的值表示不選擇或初始值

初始化 dp 陣列將每一個位置的值初始化為一個無限大的值，這裡設為 amount + 1，例如 Amount 金額為 11，使用最小 Coin 1 的硬幣數為 11 即最多硬幣數，所以 12 是不可能達到的結果。若使用 INT_MAX 要做好保護判斷不然會產生加法溢位問題)

實作：

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

但這樣只是能處理 3 種硬幣，改寫成處理各種 coins 數量後，

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

所以公式為 dp[i] = min(dp[i], 1+dp[i-coins[j]])

參考：
#322. Coin Change
https://www.bilibili.com/video/av85797996/