322. 零钱兑换

image.png

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        if len(coins) == 0 or amount == 0: return 0
        if amount < 0: return -1
        # 初始化为amount+1是因为，
        # 金额为amount最多由amount个1元硬币凑成，
        # amount +1 相当于一个正无穷，也可初始化为float('inf') 一个意思
        dp = [amount + 1] * (amount + 1) 
        dp[0] = 0
        for i in range(amount+1):
            for coin in coins:
                if i - coin < 0: 
                    continue
                dp[i] = min(dp[i], 1 + dp[i-coin])
        return dp[amount] if dp[amount] != (amount + 1) else -1

518. 零钱兑换 II

image.png

class Solution:
    def change(self, amount: int, coins: List[int]) -> int:
        if amount <= 0 : return 1
        if len(coins) == 0: return 0
        dp = [0] * (amount + 1)
        dp[0] = 1
        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = dp[i] + dp[i-coin]
        return dp[amount]