題目在問什麼

給一組硬幣面額 coins，以及目標金額 amount。每種硬幣都可以用無限次，要求湊出 amount 所需的最少硬幣數；如果無法剛好湊到，就回傳 -1。

例子

Input: coins = [1, 2, 5], amount = 11
Output: 3

因為 11 = 5 + 5 + 1。

這題不能用貪心

這題很容易先想到貪心，但它不保證正確。

原因是「先拿大面額」不一定會導向最少硬幣數。某些面額組合下，最佳解可能根本不包含當前最大的硬幣。

所以這題更穩的方向是 Dynamic Programming。

解題思路

這份寫法是記憶化 DFS。

想法是把問題轉成：

  • 要湊出 amount
  • 我可以先選任意一枚硬幣 coin
  • 然後把問題變成「湊出 amount - coin 最少要幾枚」

對每個可能的 coin 都試一次，取最小值即可。

為了避免重複計算，把每個 amount 的結果存進 memo。之後如果再次遇到同樣的剩餘金額，就直接回傳，不用整棵遞迴樹重算。

代碼

public class Solution
{
    public int CoinChange(int[] coins, int amount)
    {
        if (amount == 0) { return 0; }

        Array.Sort(coins);
        int[] memo = new int[amount];
        return ClearCoinPathCounter(coins, amount, memo);
    }

    int ClearCoinPathCounter(int[] coins, int amount, int[] memo)
    {
        if (amount == 0) { return 0; }
        if (memo[amount - 1] != 0) { return memo[amount - 1]; }

        int minValue = int.MaxValue;

        for (int i = 0; i < coins.Length; i++)
        {
            if (amount < coins[i]) { break; }

            int stepCnt = ClearCoinPathCounter(coins, amount - coins[i], memo);

            if (stepCnt >= 0 && stepCnt < minValue)
            {
                minValue = stepCnt + 1;
            }
        }

        memo[amount - 1] = minValue == int.MaxValue ? -1 : minValue;
        return memo[amount - 1];
    }
}

思路圖

複雜度

記憶化之後，每個金額狀態最多只會真正算一次。

  • 時間複雜度：O(amount * coins.Length)
  • 空間複雜度：O(amount)，主要來自 memo 和遞迴堆疊

這題先記住的重點

  • 這題不是穩定的貪心題
  • 核心是把「最少硬幣數」拆成很多個子金額問題
  • 記憶化是關鍵，不然 DFS 會重複算很多次