2019-05-31LeetCode322. 零钱兑换

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]