# 518 - Coin Change 2

解法一 - 暴力法

這題的暴力法就是要每個 coin 都嘗試用或不用，然後看這樣下去會有幾種方法，實作如下：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        return enumerate(amount, coins, 0); 
    }

private:
    int enumerate(int amount, vector<int>& coins, int curIdx){
        if(amount == 0)
            return 1;

        if(coins.empty() || curIdx >= coins.size())
            return 0;

        // Use the coin[i]
        int way1 = 0;
        if(coins[curIdx] <= amount)
            way1 = enumerate(amount-coins[curIdx], coins, curIdx);

        // Do not use coin[i]
        int way2 = enumerate(amount, coins, curIdx+1);

        return way1+way2;
    }
};

這個解法不意外地會 TLE。

解法二 - 暴力法 + memoization

我們可以用一個 2D array 來記錄已經計算過的結果，實作如下：

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        vector<vector<int>> memo(coins.size(), vector<int>(amount+1, -1));
        return enumerate(amount, coins, 0, memo); 
    }

private:
    int enumerate(int amount, vector<int>& coins, int curIdx, vector<vector<int>>& memo){
        if(amount == 0)
            return 1;

        if(coins.empty() || curIdx >= coins.size())
            return 0;

        if(memo[curIdx][amount] != -1)
            return memo[curIdx][amount];

        // Use the coin[i]
        int way1 = 0;
        if(coins[curIdx] <= amount)
            way1 = enumerate(amount-coins[curIdx], coins, curIdx, memo);

        // Do not use coin[i]
        int way2 = enumerate(amount, coins, curIdx+1, memo);

        memo[curIdx][amount] = way1+way2; 
        return memo[curIdx][amount];
    }
};

雖然可以過，但效率頗差：

Runtime: 68 ms, faster than 10.27% of C++ online submissions for Coin Change 2. Memory Usage: 22.5 MB, less than 14.29% of C++ online submissions for Coin Change 2.

解法三 - DP

經過上面的思考過程，要寫出 recurrence formula 就輕鬆不少，首先定義一下 subproblem:

dp[i][amount] = 使用 coin 0-i，組出 amount 有幾種方法

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

dp[i][amount] = dp[i-1][amount] + dp[i][amount-coins[i]]

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

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        if(coins.empty() && amount <= 0)
            return 1;

        if(amount > 0 && coins.empty())
            return 0;

        // Init
        // amount == 0, there's one way to have this amount
        vector<vector<int>> dp(coins.size(), vector<int>(amount+1, 0));
        for(int c=0; c<coins.size(); c++)
            dp[c][0] = 1;

        // only one coin, when the amount is divisible by coin[0], there's one way
        for(int a=0; a<=amount; a++) 
            dp[0][a] = (a%coins[0] == 0) ? 1 : 0;

        // Building DP table
        for(int c=1; c<coins.size(); c++) {
            for(int a=1; a<=amount; a++) {
                dp[c][a] = dp[c-1][a] + (coins[c] <= a ? dp[c][a-coins[c]] : 0);
            }
        }

        return dp[coins.size()-1][amount];
    }
};

解法四 - 優化成只用一個 row 的 DP

因為

dp[i][amount] = dp[i-1][amount] + dp[i][amount-coins[i]]

我們其實只需要 1D 的 dp array 就夠了。

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        if(coins.empty() && amount <= 0)
            return 1;

        if(amount > 0 && coins.empty())
            return 0;

        // Init
        // amount == 0, there's one way to have this amount
        vector<int> dp(amount+1, 0);
        dp[0] = 1;

        // Building DP table
        for(int c=0; c<coins.size(); c++) {
            for(int a=0; a<=amount; a++) {
                dp[a] = dp[a] + (coins[c] <= a ? dp[a-coins[c]] : 0);
            }
        }

        return dp[amount];
    }
};

效率提升不少：

Runtime: 12 ms, faster than 47.66% of C++ online submissions for Coin Change 2. Memory Usage: 8.6 MB, less than 100.00% of C++ online submissions for Coin Change 2.