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 相當(dāng)于一個正無窮，也可初始化為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]