LeetCode 322 零錢兌換：動態規劃求最少硬幣數完整解析

問題描述

給定硬幣面額數組 coins 和目標金額 amount，每種硬幣無限供應。求湊齊 amount 所需最少硬幣數，無解返回 -1。

DP 狀態定義

dp[x]：湊齊金額 x 所需最少硬幣數。
初始：dp[0]=0，其餘 INF。
轉移：dp[i] = min(dp[i], dp[i-coin] + 1) 對所有 coin ≤ i。

Java 實現

public int coinChange(int[] coins, int amount) {
    int[] dp = new int[amount + 1];
    Arrays.fill(dp, Integer.MAX_VALUE);
    dp[0] = 0;
    Arrays.sort(coins);
    for (int c : coins) if (c <= amount) dp[c] = 1;
    for (int i = 1; i <= amount; ++i) {
        if (dp[i] == 1) continue;
        for (int c : coins) {
            if (c >= i) break;
            if (dp[i-c] != Integer.MAX_VALUE)
                dp[i] = Math.min(dp[i], dp[i-c] + 1);
        }
    }
    return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
}

BFS 替代視角

將金額視為圖節點，邊為硬幣面額。從 0 開始 BFS，首次到達 amount 即最短路（最少硬幣）。適用於 amount 較大但 coins 較少的情況。

關鍵優化

• 硬幣排序，內層循環提前 break
• 預設置 dp[coin]=1 減少遞推
• Integer.MAX_VALUE 表示不可達，防溢出

複雜度

時間 O(amount × |coins|)，空間 O(amount)。amount ≤ 10⁴ 時極快。

測試樣例

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