# 322 - Coin Change

解法一 - DP

首先定義一下 subproblem:

dp[i][amount] = 使用 coin 0-i，組出 amount 最少需要幾個 coin

分成不用 coin i 跟 用 coin i 兩種情況，就可以寫出下面的 formula：

dp[i][amount] = min(dp[i-1][amount], dp[i][amount-coins[i]]+1)

初始化就是 amount == 0 的時候，這時只需要 0 個 coin 就可以了，

實作成程式碼就像下面這樣：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<vector<int>> dp(n, vector<int>(amount+1, INT_MAX));

        // Init
        for(int c=0; c<n; c++)
            dp[c][0] = 0;

        // Build DP table
        for(int c=0; c<coins.size(); c++) {
            for(int a=1; a<=amount; a++) {
                if(c > 0) {
                    dp[c][a] = dp[c-1][a];
                }
                if(a >= coins[c]) {
                    // If dp[c][a-coins[c]] == INT_MAX
                    // There's no way to use coin i to make up a
                    if(dp[c][a-coins[c]] != INT_MAX) {
                        dp[c][a] = min(dp[c][a], dp[c][a-coins[c]]+1);
                    }
                }
            }
        }

        return dp[n-1][amount] == INT_MAX ? -1 : dp[n-1][amount];
    }
};

解法二 - 優化版 DP

這題一樣可以只使用 1D dp array，實作如下：

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n = coins.size();
        vector<int> dp(amount+1, INT_MAX);

        dp[0] = 0;

        for(int c=0; c<coins.size(); c++) {
            for(int a=1; a<=amount; a++) {
                if(a >= coins[c]) {
                    if(dp[a-coins[c]] != INT_MAX) {
                        dp[a] = min(dp[a], dp[a-coins[c]]+1);
                    }
                }
            }
        }

        return dp[amount] == INT_MAX ? -1 : dp[amount];
    }
};