322. 零錢兌換
標(biāo)簽: 動態(tài)規(guī)劃
給定不同面額的硬幣 coins 和一個總金額 amount豌骏。編寫一個函數(shù)來計算可以湊成總金額所需的最少的硬幣個數(shù)吓著。如果沒有任何一種硬幣組合能組成總金額薄翅，返回 -1兔综。
示例1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例2:
輸入: coins = [2], amount = 3
輸出: -1
思路
'''
1. 觀察到題目主要問題可以劃分成規(guī)模更小子問題, 采用動態(tài)規(guī)劃思想解題
2. 先確定狀態(tài): 假設(shè)金額為i所需的最少硬幣個數(shù)為counts[i]
2.1 從最后一步考慮: counts[amount] = min(counts[amount-coins[0],counts[amount-coins[1]] ...]) + 1
2.2 則原問題可分解成為更小的子問題
3. 則我們可以確定其動態(tài)方程:counts[i] = min([counts[i-coins[j]] for j in coins]) + 1
4. 我們需要確定起始條件和邊界條件:
起始條件: counts[0] = 0
邊界條件: i >= 0
5. 求解順序: 從0到amount
'''
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
costs = [-1] * (amount + 1)
costs[0] = 0
for i in range(1, amount + 1):
lst = [costs[i-coin] for coin in coins if i-coin >= 0 and costs[i-coin]!= -1]
costs[i] = min(lst) + 1 if lst else -1
return costs[-1] 