Leetcode No.322(Coin Change) 心得(Medium)

5 min readSep 5, 2017

題目:
You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

Credits:
Special thanks to @jianchao.li.fighter for adding this problem and creating all test cases.

想法:
這題看起來很簡單，我的想法是用 Greedy 方法，也就是從最大的 coin 面額拿最多的硬幣開始，多的部分從次大的面額開始拿起，以此類推。如果這個數目無法滿足，那麼從最大的面額數目減一，再重複步驟。

結果這個方法是錯的!! 因為不保證大面額硬幣拿最多的數目就是最佳解。原因是有可能剩下的部分只能讓小面額來滿足，這樣硬幣數目會很多，說不定大面額再少一，就可以讓次大面額的滿足剩下的數目，這樣需要的硬幣數反而更少。所以變成要遍尋所有可能找到 Min 再回傳，然後就 Time Limit Exceeded。

這裡我就不貼我的解法了，因為他相當於網路上的第一個方法。

網路上的解法:
這提的標準解法是用 DP。只是差別是要用 DP Recursive or DP Iteration。
DP 的核心概念就是大問題有個最佳解，那我可以把它分解成一個或幾個小問題，這些小問題也有最佳解，依序下去。
這題的大問題就是 F(amount) = MinCoins
可以推論 F(amount - coins[i]) = MinCoins-1
F(amount) = F(amount - coins[i]) + 1
這樣就可以縮小問題了。
這裡可以用減法，縮成小問題，或者可以用加法，從小問題的解法推到大問題。
(這題用加法要注意 int overflow，因為 total amount = INT.MAX -1 的話，amount + coin 會 overflow)

這邊提醒一下，因為越小的問題被重複呼叫的機率很大，所以可以暫存起來，或者 hardcode。
暫存就要注意記憶體會不會過大，input 的範圍匯到哪裡。

Recursive解法(Top-Down):

public class Solution {    public int coinChange(int[] coins, int amount) {        
        if (amount < 1) return 0;
        return coinChange(coins, amount, new int[amount]);
    }    private int coinChange(int[] coins, int rem, int[] count) {
        if (rem < 0) return -1;
        if (rem == 0) return 0;
        if (count[rem - 1] != 0) return count[rem - 1];
        int min = Integer.MAX_VALUE;
        for (int coin : coins) {
            int res = coinChange(coins, rem - coin, count);
            if (res >= 0 && res < min)
                min = 1 + res;
        }
        count[rem - 1] = (min == Integer.MAX_VALUE) ? -1 : min;
        return count[rem - 1];
    }
}

Iteration解法(bottom-up):

public class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = amount + 1;             
        int[] dp = new int[amount + 1];  
        Arrays.fill(dp, max);  
        dp[0] = 0;   
        for (int i = 1; i <= amount; i++) {
            for (int j = 0; j < coins.length; j++) {
                if (coins[j] <= i) {
                    dp[i] = Math.min(dp[i], dp[i - coins[j]] + 1);
                }
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
}

我的程式:

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        vector<int> minCoinNum(amount+1, -1);
        
        minCoinNum[0] = 0;
        
        for (int i = 0; i <= amount; i++) {
            for (auto coin: coins) {
                if (i-coin < 0 || minCoinNum[i-coin] == -1) {
                    continue;
                }
                
                if (minCoinNum[i] == -1 || minCoinNum[i-coin]+1 < minCoinNum[i]) {
                    minCoinNum[i] = minCoinNum[i-coin] + 1;
                }
            }
        }
        
        return minCoinNum[amount];
    }
};

Leetcode No.322(Coin Change) 心得(Medium)

Written by ChingYuanYang