題目網址：https://leetcode.cn/problems/coin-change/

題意：給一整數 array coins, 表示不同面額的零錢, 和一整數 amount 代表總金額。

計算可以湊成 amount 的最少硬幣數。如果無法湊成, 則返回 -1。

每種硬幣的數量都是無限的。

Solution 1：（TLE 無法通過）

想法：利用 DFS

  • 普通版：DFS

    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            int res = amount + 1, count = 0;
            dfs(coins, amount, count, res);
            return (res == amount + 1) ? -1 : res;
        }

    private:
        void dfs(const vector<int>& coins, const int amount, const int count, int& res){
            if (amount == 0) {
                res = min(count, res);
                return;
            } else if (amount < 0) {
                return;
            }

            for (const auto& coin : coins) {
                if (amount >= coin) {
                    dfs(coins, amount - coin, count + 1, res);
                }
            }
        }
    };

  • 進階版：DFS + greedy（每次取最大面額）+ pruning

    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            // sort coins in descending order
            sort(coins.rbegin(), coins.rend());
            int res = amount + 1;
            dfs(coins, 0, amount, 0, res);
            return (res == amount + 1) ? -1 : res;
        }
    private:
        void dfs(const vector<int>& coins, const int idx, const int amount, const int count, int& res) {
            if (amount == 0) {
                res = min(res, count);
                return;
            }

            if (idx == coins.size()) {
                return;
            }

            const int coin = coins[idx]; // 每次取最大面額的硬幣
            for (int k = amount / coin; k >= 0 && count + k < res; --k) {
                dfs(coins, idx + 1, amount - k * coin, count + k, res);
            }
        }
    };

Solution 2：

想法：改進 Solution 1, 利用 DP 來避免重複計算（圖中綠色圈起來的部分）, 其中 dp[i] 為湊齊金額 i 的最少硬幣數

class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        /*
         * 金額範圍 : 0 ~ amount (amount + 1 種), 每種金額的最少硬幣數初始為 amount + 1
         * 若 coins 中的硬幣面額能湊齊金額 i, 則 dp[i] 一定小於 amount (因為面額最小為 1)
         * 故初始值故意設成大於 amount 的數 (amount + 1), 用一個不可能的數代表無法湊齊
         * 這樣當 dp[i] == amount + 1 時, 代表無法用 coins 中的硬幣面額湊齊金額 i
         */
        vector<int> dp(amount + 1, amount + 1);
        dp[0] = 0; // 湊齊金額 0 的最少硬幣數為 0

        for (int i = 1; i <= amount; ++i) {
            for (const auto& coin : coins) {
                if (i >= coin) {
                    dp[i] = min(dp[i], 1 + dp[i - coin]);
                }
            }
        }
        return (dp[amount] == amount + 1) ? -1 : dp[amount];
    }
};
  • time：$O(amount \cdot n)$ ➔ for loop, 其中 n 為硬幣的種類
  • space：$O(amount)$ ➔ dp