LeetCode 322. [Python] Coin Change
原题链接
中等
作者:
徐辰潇
,
2021-01-31 01:21:09
,
所有人可见
,
阅读 508
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
#DP: dp[i] means the smallest amount of coints to reach total amount i
#dp[i] = -1 means impossible combination of coins to reach total amount i
#TC: O(len(coins)*amount)
#SC: O(amount)
dp = [-1]*(amount+1)
dp[0] = 0
for t in range(1, amount+1):
for c in coins:
if t - c >= 0 and dp[t-c] != -1:
if dp[t] == -1:
dp[t] = dp[t-c] + 1
else:
dp[t] = min(dp[t], dp[t-c] + 1)
return dp[-1]
这个点莫非是海外..
Yes
Yesss! expecting more! Python Sooo Cooooool