Posted on 2023-08-11 15:47
Uriel 阅读(24)
评论(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]