322. Coin Change

──────────────────────────────────────────────────────────────────────

322. Coin Change

給定總金額 amount 和硬幣面額 coins（每種面額數量無限），問湊出 amount 最少要幾枚硬幣，湊不出來就回傳 -1。

例如金額 11、面額 [1, 2, 5]，最少是兩枚 5 加一枚 1，答案 3。如果金額是 3 而面額只有 [2]，湊不出來，回傳 -1。

思路

先說為什麼貪心是錯的

生活經驗會說「盡可能先用最大面額，不夠再往次大的找」。這個直覺很強，但這題不成立，原因有三個層次：

1. 題目沒有保證 coins 是排好序的
2. 先用大面額可能導致剩下的金額根本湊不出來，還要能退回去重試
3. 就算處理掉前兩點，貪心本身就是錯的

第三點才是關鍵，一個反例就夠：

coins = [1, 3, 4], amount = 6

貪心：4 → 剩 2 → 1 → 1      3 枚
最佳：3 + 3                 2 枚

貪心在第一步拿走 4，而 4 這個選擇讓剩下的 2 只能用兩個 1 湊。根本原因是面額之間可以互相取代：4 和 3+1 都是 4 塊錢，但它們對「剩下要湊多少」的影響完全不同，而你在拿的當下無從判斷。

只要一題出現「這一步選什麼，會改變剩下能選什麼的組合」，貪心就不成立 —— 判斷方式見 Greedy 模板。這題也正是那篇拿來當反例的題目。

貪心不行，那就窮舉

既然沒辦法在當下判斷，那就每種面額都試一次，讓電腦去窮舉。遞迴式非常直白：

$$f(remaining)=1+\underset{coin\in coins}{\min }f(remaining-coin)$$

「湊出 remaining 最少要幾枚」＝「先拿一枚（不管拿哪種），再湊剩下的」，取所有選法裡最小的那個。

邊界條件有三種：

• remaining < 0 —— 拿爆了，這條路不通，回 -1
• remaining == 0 —— 剛好湊完，回 0
• 其他 —— 繼續遞迴

解題方向

純遞迴（會超時）

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        def helper(remaining):
            if remaining < 0:
                return -1
            elif remaining == 0:
                return 0
            else:
                # f(remaining) = 1 + min(f(remaining-coin[1]), ..., f(remaining-coin[n]))
                min_cost = float('inf')
                for coin in coins:
                    res = helper(remaining - coin)
                    if res != -1:
                        min_cost = min(min_cost, res + 1)
                if min_cost != float('inf'):
                    return min_cost
                else:
                    return -1
        return helper(amount)

float('inf') 當哨兵，代表「目前還沒找到任何可行解」。最後如果它沒被更新過，就代表所有面額都走不通，回 -1。

這份程式碼是正確的，但會超時 —— 因為同一個 remaining 會被重複計算很多次。以 coins = [1, 2, 5] 為例，f(9) 可以從 11 - 2 到達，也可以從 11 - 1 - 1 到達，兩條路各算一遍。

Top-Down：加上 @cache

能記憶化的前提是：f(remaining) 只跟 remaining 有關，跟「你是怎麼走到這個 remaining 的」完全無關。 確認了這件事，加一行裝飾器就好：

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:

        @cache
        def helper(remaining):
            if remaining < 0:
                return -1
            if remaining == 0:
                return 0
            min_cost = float('inf')
            for coin in coins:
                res = helper(remaining - coin)
                if res != -1:
                    min_cost = min(min_cost, res + 1)
            return min_cost if min_cost != float('inf') else -1

        return helper(amount)

@cache 做的事就是「查表 → 沒有就算 → 存回去」，跟手寫一個字典一模一樣。但它有一個手寫版容易忘記的好處：-1 也會被快取。手寫的時候如果只在找到答案時才存進字典，那些湊不出來的分支會被反覆重算，記憶化等於白做。

@cache 來自 functools，用法見 Python 面試技巧。

Bottom-Up

Top-down 是「從 amount 往下拆」，bottom-up 反過來 —— 從 0 開始，一路把每個金額的答案都填出來，填到 amount 就結束。

dp[i] 的定義是：湊出金額 i 最少要幾枚硬幣。

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        # 如果沒有最佳解，則該解為無限大
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for i in range(len(dp)):
            for coin in coins:
                if i - coin >= 0:
                    dp[i] = min(dp[i], 1 + dp[i-coin])

        return -1 if dp[amount] == float('inf') else dp[amount]

dp[0] = 0 是唯一的起點：湊出 0 塊需要 0 枚。之後每個 dp[i] 都只依賴比它小的格子，所以由小往大填一定填得完。

float('inf') 在這裡同時扮演兩個角色：初始值（還沒算出來）和「湊不出來」的標記。因為 1 + inf 還是 inf，湊不出來的狀態會自動往後傳播，不需要特別處理。

外層跑金額、內層跑硬幣 —— 這題兩層迴圈交換順序不影響答案，因為求的是最少個數。但在 518. Coin Change 2 求「有幾種湊法」時，順序交換就會把答案從「組合數」變成「排列數」。那是背包題最經典的坑。

補充

背包三形態（見總索引）：

題目	背包類型	問什麼
322	完全背包（每種無限用）	最少幾個
518. Coin Change 2	完全背包	有幾種湊法
416. Partition Equal Subset Sum	0/1 背包（每個用一次）	可不可行

三題的狀態轉移幾乎一樣，差別全在「迴圈順序」和「要 min、要加總、還是要 or」。放在一起寫最能看出差異。

貪心什麼時候才對？ 台幣、美元這種面額（1、5、10、50、100…）貪心確實是對的，這類幣制有個名字叫 canonical coin system。但那是幣制的性質，不是問題的性質 —— LeetCode 會給你任意面額，所以不能靠它。

複雜度

以下都用 $A$ 表示 amount、$k$ 表示面額的種類數。

• 純遞迴 — 時間 $O(k^A)$，每層展開 $k$ 個分支、深度最多 $A$；空間 $O(A)$ 是遞迴深度
• Top-down（@cache） — 時間 $O(A\times k)$，狀態只有 $A+1$ 個，每個狀態試 $k$ 種面額；空間 $O(A)$ 是快取加上遞迴堆疊
• Bottom-up — 時間 $O(A\times k)$ 一樣；空間 $O(A)$ 只有 dp 陣列，沒有遞迴堆疊

兩種 DP 寫法複雜度相同，bottom-up 的常數比較小而且不會有遞迴深度的問題。