LeetCode 322 Coin Change 零錢兌換：動態規劃與 DFS 剪枝優化

題目描述

給定不同面額硬幣 coins 及總金額 amount，求湊成總額所需最少硬幣數。無解返回 -1。每種硬幣無限供應。

範例

coins = [1,2,5], amount = 11 → 3 (5+5+1)
coins = [2], amount = 3 → -1

解法一：動態規劃（自底向上）

狀態定義

dp[x] = 湊成金額 x 的最少硬幣數。初始 dp[0]=0，其餘設為 amount+1（作為無窮大）。

轉移方程

for x = 1..amount:
    for coin in coins:
        if coin <= x:
            dp[x] = min(dp[x], dp[x-coin] + 1)

代碼

class Solution {
public:
    int coinChange(vector& coins, int amount) {
        vector dp(amount + 1, amount + 1);
        dp[0] = 0;
        for (int x = 1; x <= amount; ++x) {
            for (int c : coins) {
                if (c <= x) dp[x] = min(dp[x], dp[x - c] + 1);
            }
        }
        return dp[amount] > amount ? -1 : dp[amount];
    }
};

解法二：DFS + 剪枝（更快）

核心思想

• 硬幣面額排序（大到小）。
• 優先使用大面額，盡快找到可行解建立上界 best。
• 剪枝條件：當前數量 + 剩餘金額/最大面額 ≥ best 則放棄該分支。

代碼

class Solution {
    int best = -1;
    void dfs(vector::iterator begin, vector::iterator end, int amount, int count) {
        if (amount == 0) {
            best = (best == -1) ? count : min(best, count);
            return;
        }
        if (begin == end) return;
        int coin = *begin;
        if (best != -1 && count + amount / coin >= best) return; // 剪枝
        
        int maxUse = amount / coin;
        for (int use = maxUse; use >= 0; --use) {
            dfs(begin + 1, end, amount - use * coin, count + use);
        }
    }
public:
    int coinChange(vector& coins, int amount) {
        sort(coins.begin(), coins.end(), greater());
        dfs(coins.begin(), coins.end(), amount, 0);
        return best;
    }
};

複雜度比較

總結

DP 是標準解法，穩定可靠；DFS 剪枝在特定數據分佈下極快，適合競賽優化。理解兩者思路有助於應對變體問題。