322. 零錢(qián)兌換
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是因?yàn)椋? # 金額為amount最多由amount個(gè)1元硬幣湊成阔墩，
# amount +1 相當(dāng)于一個(gè)正無(wú)窮，也可初始化為float('inf') 一個(gè)意思
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. 零錢(qián)兌換 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]
