⚠️ 舊文提醒：本文發佈於約 4 年前，部分內容或指令可能已過時，請斟酌參考。
題目在此 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 = 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]
|
也許你也會想看看