Posted on 2023-08-11 15:47
Uriel 閱讀(39)
評論(0) 編輯 收藏 引用 所屬分類:
DP 、
閑來無事重切Leet Code
有若干面值的硬幣coins，問湊成amount有幾種方法，背包問題
1 #518
2 #Runtime: 63 ms (Beats 99.47%)
3 #Memory: 13.5 MB (Beats 92.73%)
4
5 class Solution(object):
6 def change(self, amount, coins):
7 """
8 :type amount: int
9 :type coins: List[int]
10 :rtype: int
11 """
12 dp = [0] * (amount + 1)
13 dp[0] = 1
14 for c in coins:
15 for j in range(c, amount + 1):
16 dp[j] += dp[j - c]
17 return dp[-1]