LeetCode 筆記 - 322. Coin Change

Posted on

題目在此 322. Coin Change

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

解題思維

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

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

完成 🥰

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
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]

相關文章