python換零錢_LeetCode-python 322.零錢兌換

題目連結

難度：中等       類型：動态規劃

給定不同面額的硬币 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬币個數。如果沒有任何一種硬币組合能組成總金額，傳回 -1。

示例1

輸入: coins = [1, 2, 5], amount = 11

輸出: 3

解釋: 11 = 5 + 5 + 1

示例2

輸入: coins = [2], amount = 3

輸出: -1

解題思路

dp[i]表示湊成總金額i需要的最少硬币個數

如例1中coins=[1,2,5]，dp[1],dp[2]和dp[5]都等于1，因為用相應金額的一枚硬币就能組成i。

對于其他的i,例如i = 11, dp[11] = min(dp[11-1], dp[11-2], dp[11-5])+1

dp[i]隻有這兩種更新方式 ，有可能amount無法用coins裡的硬币構成，那麼，初始化每個dp[i]的時候都為amount,若dp[amount]=amount,傳回-1

代碼實作

class Solution(object):

def coinChange(self, coins, amount):

"""

:type coins: List[int]

:type amount: int

:rtype: int

"""

dp = [0]*(amount+1)

coins.sort()

for i in range(1,amount+1):

if i in coins:

dp[i] = 1

continue

min_val = amount

for coin in coins:

if i>=coin:

min_val = min(min_val, dp[i-coin])

else:

break

dp[i] = min_val+1

return dp[amount] if dp[amount]<=amount else -1