LeetCode 筆記 - 322. Coin Change

題目在此 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]

也許你也會想看看