322. Coin Change刷题笔记

用自底向上的dp算法

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0] + [float('inf')]*amount
        for i in range(1,amount+1):
            for coin in coins:
                if i-coin >= 0:
                    dp[i] = min(dp[i],dp[i-coin]+1)
                    
        if dp[-1]>100000:
            return -1
        else:
            return dp[-1]