Python 解決找零錢問題：貪心算法與動態規劃實現

問題描述

硬幣面值 25、10、1 分，輸入金額 n（分），求最少硬幣數。

貪心算法（適用於標準幣制）

def min_coins_greedy(n: int) -> int:
    coins = [25, 10, 1]
    count = 0
    for c in coins:
        count += n // c
        n %= c
    return count

標準幣制（每種面值是下一面值的整數倍或經典貨幣系統）貪心策略最優。

動態規劃（通用解法）

def min_coins_dp(n: int) -> int:
    coins = [25, 10, 1]
    dp = [float('inf')] * (n + 1)
    dp[0] = 0
    for i in range(1, n + 1):
        for c in coins:
            if c <= i:
                dp[i] = min(dp[i], dp[i - c] + 1)
    return dp[n]

時間 O(n·k)，空間 O(n)，適用於任意面值組合。

測試用例

for n in [0, 1, 5, 10, 25, 30, 41, 99, 100]:
    print(f"{n}分 -> 貪心: {min_coins_greedy(n)}, DP: {min_coins_dp(n)}")

輸出驗證兩算法在標準幣制下結果一致。

總結

面試/作業首選貪心 O(k) 簡潔高效；若面值非常規（如 25, 20, 1），必須用 DP 保證最優。Python 列表推導與無限大常數使代碼極具可讀性。