Greedy · 02 / 05

Coin Change (Greedy)找零問題

標準幣值可以貪，任意幣值會錯。

用在：收銀找零、理解貪婪何時會失敗

時間複雜度O(n)

空間複雜度O(1)

難度入門

前置知識Greedy Principles

01為什麼需要它

收銀機找零

客人付了 100 元買 37 元的東西，要找 63 元。收銀員不會列舉所有組合，而是從最大的面額開始拿：50、10、1、1、1，五個硬幣。這個做法在台幣、美金、歐元上都對。

為什麼用它這正是貪婪：每次拿不超過剩餘金額的最大面額。它對，是因為這些幣制設計成「大面額是小面額的整數倍或接近整數倍」，拿大的永遠不會比拿小的差。這一課先確認它為什麼對，再看它什麼時候會錯。

自動販賣機的硬幣槽

某台販賣機只裝了 1、3、4 元三種硬幣。要找 6 元，貪婪會給 4+1+1 三枚，但其實 3+3 兩枚就夠。硬幣槽會提早用光。

為什麼用它同一個貪婪演算法，換一組幣值就錯了。這是貪婪法最重要的教訓：正確性來自輸入的結構，不是來自演算法本身。判斷幣值能不能貪，有一個明確的檢查方法。

任意幣值的最少硬幣數

面試題給你任意面額陣列和金額，問最少幾枚。看起來像找零，但幣值沒有保證，貪婪會在某些測資上錯。

為什麼用它這時候要用 DP：dp[a] 是湊出 a 元最少幾枚，對每個面額 c 試 dp[a − c] + 1。貪婪是 DP 的特例，當幣制是標準幣制時，DP 每一步的最佳轉移剛好就是「拿最大的」。

看到這些關鍵字就想到它：找零、最少硬幣、面額由大到小、標準幣制、貪婪會錯就轉 DP。

02核心概念

找零的貪婪解只有一個規則：面額由大到小，每一種都拿到剩餘金額不夠為止。實作是一個迴圈，每種面額做一次整數除法和取餘數，O(k)，k 是面額種類數。它不看其他組合，所以快到幾乎沒有成本。

它在 [1, 5, 10, 50] 這類幣制上是對的，直覺理由是：任何最佳解裡，小面額硬幣的數量都有上限（1 元最多 4 枚、5 元最多 1 枚、10 元最多 4 枚），超過上限就能換成更少枚的大面額。這些上限加起來湊不到下一個大面額，所以只要剩餘金額夠大，最佳解一定含有那個大面額，貪婪拿它不會錯。這就是交換論證：把最佳解裡「幾枚小的」換成「一枚大的」，枚數只會更少。

[1, 3, 4] 找 6 元時貪婪錯了：拿 4 之後剩 2，只能用兩個 1，共三枚，但 3+3 只要兩枚。交換論證在這裡失敗，因為兩枚 3 元不能換成一枚更大的。這種幣制叫非標準幣制。判斷一組幣值是不是標準幣制，Kozen 與 Zaks 證明最小的反例一定小於最大兩個面額之和，所以只要在那個範圍內把貪婪和 DP 比一遍就能確定，不需要無窮檢查。

貪婪錯的時候，正確解是 DP：dp[a] = min(dp[a − c] + 1)，對所有面額 c ≤ a。時間 O(amount × k)，空間 O(amount)。常見誤區是在 LeetCode 322 這種「任意面額」的題目上寫貪婪，測資裡就有 [1, 3, 4] 型的反例。反過來，若題目明說是標準幣制，或者面額彼此是倍數關係（[1, 2, 4, 8]），貪婪就是正確而且最快的解。

03演算法步驟

1把面額由大到小排序。
2對每種面額 c：count = amount // c，拿 count 枚，amount %= c。
3迴圈結束時 amount 應該是 0；不是 0 代表這組面額湊不出這個金額（有 1 元時不會發生）。
4要確認這組幣值能不能貪：對 1 到「最大兩個面額之和」的每個金額，比較貪婪和 DP 的枚數，全部相同就是標準幣制。
5不是標準幣制，就改用 DP：dp[0] = 0，dp[a] = min(dp[a − c] + 1)，最後看 dp[amount]。

04互動示範

切換兩組幣值和四個金額。貪婪每一步拿一種面額，右側是 DP 算出的最佳解。留意 [1, 3, 4] 找 6 元和 10 元的結果，以及 27 元為什麼又剛好對了：反例不是每個金額都出現，所以幾筆測資通過不代表演算法正確。

幣值

金額

greedy(6)面額由大到小，能拿就拿

面額（由大到小）

431

剩餘金額

6/ 6

貪婪拿的硬幣（0 枚）

還沒拿

最佳解，DP 算的（2 枚）

步驟 0/4要找 6 元。貪婪：面額由大到小，每一種都盡量多拿，拿到剩餘金額不夠為止。

05程式碼

貪婪版、DP 版，以及判斷幣值是否為標準幣制的檢查函式。三個函式合起來就是這一課的結論：能貪就貪，不能貪就 DP，而且有辦法事先知道能不能貪。

# 貪婪找零：面額由大到小，每種盡量多拿
def coin_change_greedy(coins, amount):
    coins = sorted(coins, reverse=True)
    result = []
    for c in coins:
        count, amount = divmod(amount, c)      # 這種面額最多拿幾枚，剩多少
        result += [c] * count
    return result if amount == 0 else None    # 剩下不是 0 代表湊不出來


# DP 找零（LeetCode 322）：任何幣值都對，O(amount × 面額數)
def coin_change_dp(coins, amount):
    INF = float("inf")
    dp = [0] + [INF] * amount                 # dp[a] = 湊出 a 元最少幾枚
    for a in range(1, amount + 1):
        for c in coins:
            if c <= a and dp[a - c] + 1 < dp[a]:
                dp[a] = dp[a - c] + 1
    return dp[amount] if dp[amount] != INF else -1


# 判斷一組幣值是不是「標準幣制」（貪婪永遠正確）
# Kozen 與 Zaks 證明：若貪婪會錯，最小的反例一定小於最大兩個面額之和
def is_canonical(coins):
    coins = sorted(coins)
    limit = coins[-1] + coins[-2]
    for amount in range(1, limit):
        g = coin_change_greedy(coins, amount)
        if g is None or len(g) != coin_change_dp(coins, amount):
            return False
    return True


if __name__ == "__main__":
    print(coin_change_greedy([1, 5, 10, 50], 63))   # [50, 10, 1, 1, 1]
    print(coin_change_greedy([1, 3, 4], 6))          # [4, 1, 1]，但最佳是 [3, 3]
    print(coin_change_dp([1, 3, 4], 6))              # 2
    print(is_canonical([1, 5, 10, 50]), is_canonical([1, 3, 4]))   # True False

06練習題

LeetCode 860Lemonade Change（找零時先拿大的）Easy
LeetCode 1710Maximum Units on a Truck（按單位價值排序）Easy
LeetCode 322Coin Change（任意面額，要用 DP）Medium
LeetCode 518Coin Change II（方法數，DP）Medium
LeetCode 279Perfect Squares（貪婪會錯的另一個例子）Medium

上一篇Greedy Principles 下一篇Interval Scheduling