LeetCode 筆記 - 322. Coin Change

解析經典的零錢兌換問題。本文探討如何運用動態規劃（Dynamic Programming）建立遞迴關係式，透過查表法記錄組合出每個目標金額所需的最少錢幣數量。這是一個理解 DP 如何將大問題分解為子問題並重複利用結果的優質範例。

發佈: 2022.05.21
閱讀: 約 1 分鐘
字數: 259

⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。

題目在此 322. Coin Change

給你錢幣種類跟目標數，請找出個數最少的錢幣組合可以組合出目標數

解題思維

這種組合型題目，就是請 Dynamic programming 出場的時候了

先宣告一個表格，每格內的數字代表的意義是 index 個數最少的錢幣組合
所以當我們來到 n 的時候，就看 n - (各種錢幣) 的哪一格的個數最少
接著 + 1 就是 n 的答案

完成 🥰

程式碼

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        result = 0
        max_amount = amount + 1
        
        # count = [amount + 1] * (amount + 1)
        count = collections.defaultdict(lambda: max_amount)
        count[0] = 0
        
        for a in range(min(coins), max_amount):
            for c in coins:
                if (diff := a - c) < 0:
                    continue
                count[a] = min(count[a], count[diff] + 1)
        
        if count[amount] == max_amount:
            return -1
        return count[amount]

也許你也會想看看