leetcode筆記：Coin Change

一. 題目描述

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.

二. 題目分析

題目大意是，給定不同面值的硬幣（數值存放在數組coins）和一個金額總值amount。編寫函數計算湊齊金額總值所最少需要的硬幣數目。如果使用已有的硬幣無法湊齊指定的金額，返回-1。

對於本題目，若使用貪心算法是不可行的，因為有可能會錯過全局最優解。

該問題可使用動態規劃來解決，構建一個數組dp[amount + 1]用於記錄從0 ~ amount每個數用coins組合的最小次數（對於每個數，組合次數的上限不可能超過amount + 1，因此可將數組初始化為amount + 1，這樣，對於某一下標i，只要出現合法的組合，就可以使用min函數覆蓋掉amount + 1，若執行算法後該下標所對應的值仍為amount + 1，說明無法在coins中找出一個組合來表示i）

根據以上思路，可寫出狀態轉移方程：

dp[x + coins] = min(dp[x] + 1, dp[x + coins])

其中dp[x]代表湊齊金額x所需的最少硬幣數，coins表示可用的硬幣面值，在coins數組中遍歷。

注意在算法執行前，令dp[0] = 0。

discuss中給出了更高效的深搜方法，相對來說代碼比較復雜，如下方第二段代碼所示。

三. 示例代碼

// DP，時間復雜度：O(n*amount)
class Solution {
public:
    int coinChange(vector& coins, int amount) {
        if (amount < 0) return -1;
        if (amount == 0) return 0;
        // 硬幣組合個數不可能大於amount，因此若某下標的元素值
        // 為amount + 1說明無法用coins裡的硬幣組合出該下標
        vector dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int i = 1; i < amount + 1; ++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];
    }
};

// DFS
class Solution {
public:
    int currBestResult;

    void solve(const vector::iterator & begin, const vector::iterator & end, int amount, int currCount)
    {
        // find a solution, update currBestResult if this is better
        if(amount == 0) {
            if(currBestResult == -1)
                currBestResult = currCount;
            else
                currBestResult = min(currBestResult, currCount);
            return;
        }

        // use up all coin types, no solution
        if(begin == end) return;
        // can't achiveve a solution better than currBestResult, no need to explore more
        if(currBestResult != -1 && currBestResult <= amount / *begin + currCount) return;

        int count, currAmount;
        // start from the largest remaining coin first
        for (auto it = begin; it != end; ++it) {
            int coin = *it;
            // use coin as much as possible, so that we can get a good solution early to save exploration
            currAmount = amount % coin;
            count = amount / coin;
            while(currAmount < amount) {
                // find solutions to fill currAmount with smaller coins
                solve(it + 1, end, currAmount, count + currCount);
                // scale back by one largest coin to extend currAmount to try solve again in the next iteration
                currAmount += coin;
                count--;
            }
        }
    }

    int coinChange(vector& coins, int amount) {
        currBestResult = -1;
        sort (coins.begin(), coins.end(), greater());
        solve(coins.begin(), coins.end(), amount, 0);   
        return currBestResult;
    }
};

四. 小結

動態規劃的經典題目，值得學習。