2019-05-31LeetCode322. 零钱兑换
2019-05-31 本文已影响0人
mztkenan
10%
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp=[float('inf') for i in range(amount+1)]
dp[0]=0
for i in range(amount+1):
for value in coins:
if i>=value:
dp[i]=min(dp[i],dp[i-value]+1)
if dp[amount]==float('inf'):dp[amount]=-1
return dp[amount]
用列表生成器会变快。。。
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
dp=[float('inf') for i in range(amount+1)]
dp[0]=0
for i in range(1,amount+1):
dp[i]=min([dp[i-c] if i>=c else float('inf') for c in coins])+1
if dp[amount]==float('inf'):dp[amount]=-1
return dp[amount]
