題目鏈接
難度：中等 ??????類型：動(dòng)態(tài)規(guī)劃
給定不同面額的硬幣 coins 和一個(gè)總金額 amount。編寫一個(gè)函數(shù)來計(jì)算可以湊成總金額所需的最少的硬幣個(gè)數(shù)宵荒。如果沒有任何一種硬幣組合能組成總金額，返回 -1琐旁。
示例1
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例2
輸入: coins = [2], amount = 3
輸出: -1
解題思路
dp[i]表示湊成總金額i需要的最少硬幣個(gè)數(shù)
如例1中coins=[1,2,5]蟆炊，dp[1],dp[2]和dp[5]都等于1堕澄，因?yàn)橛孟鄳?yīng)金額的一枚硬幣就能組成i僵芹。
對于其他的i,例如i = 11, dp[11] = min(dp[11-1], dp[11-2], dp[11-5])+1
dp[i]只有這兩種更新方式 处硬，有可能amount無法用coins里的硬幣構(gòu)成，那么拇派，初始化每個(gè)dp[i]的時(shí)候都為amount,若dp[amount]=amount,返回-1
代碼實(shí)現(xiàn)
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
