一、 零錢兌換：硬幣的最少個數(shù)

• 給一個整數(shù)數(shù)組 coins ，表示不同面額的硬幣；以及一個整數(shù) amount ，表示總金額。

• 計算并返回可以湊成總金額所需的最少硬幣個數(shù) 。如果沒有任何一種硬幣組合能組成總金額，返回-1 。

• 可認為每種硬幣的數(shù)量是無限的。

解題關(guān)鍵點

• 經(jīng)典的動態(tài)規(guī)劃問題。

• 設(shè)置一個數(shù)組dp，其中每個元素dp[i]記錄的是，當金額為i時，所需要的硬幣個數(shù)。則題目所求為dp[amount]。

• 考慮基礎(chǔ)簡單的例子。有dp[0] = 0，也就是說，金額為0所需的硬幣個數(shù)是0。

• 考慮狀態(tài)轉(zhuǎn)移公式。從小到大遍歷金額數(shù)，這樣，可以保證：當我們計算金額i所需的最少硬幣個數(shù)dp[i]時，前面更少的金額所需要的最少硬幣個數(shù)，比如dp[i-1]、dp[i-2]······等都已求出。

• 那么，對任意的dp[i]，面對某種硬幣的面額（記為coin），如果在湊成金額i時選擇了這枚硬幣，那么在湊成金額（i-coin）時所需要的硬幣個數(shù) + 1即可。也就是dp[i] = dp[i-coin] + 1。

class?Solution(object):
????def?coinChange(self,?coins,?amount):
????????"""
????????:type?coins:?List[int]
????????:type?amount:?int
????????:rtype:?int
????????"""
????????#?初始化為正無窮大
????????dp?=?[float('inf')]*(amount+1)
????
????????#?金額為0，所要湊的硬幣個數(shù)也為0
????????dp[0]?=?0
????????
????????for?coin?in?coins:
????????????sum_coin?=?coin
????????????
????????????while?sum_coin?????????????????dp[sum_coin]?=?min(dp[sum_coin],?dp[sum_coin-coin]+1)
????????????????sum_coin?+=?1
????????
????????#?print(dp)
????????return?dp[amount]?if?dp[amount]!=?float('inf')?else?-1

二、零錢兌換：硬幣的組合總數(shù)

• 給一個整數(shù)數(shù)組 coins 表示不同面額的硬幣，另給一個整數(shù) amount 表示總金額。

• 計算并返回可以湊成總金額的硬幣組合數(shù)。如果任何硬幣組合都無法湊出總金額，返回 0 。

• 假設(shè)每一種面額的硬幣有無限個。

解題關(guān)鍵點

• 經(jīng)典的動態(tài)規(guī)劃問題。

• 設(shè)置一個數(shù)組dp，其中每個元素dp[i]記錄的是，當湊成金額為i時，所有的硬幣組合的總數(shù)。則題目所求為dp[amount]。

• 考慮基礎(chǔ)簡單的例子。有dp[0] = 1，也就是說，金額為0時，只有1種選擇，就是什么硬幣都不取。

• 考慮狀態(tài)轉(zhuǎn)移公式。從小到大遍歷金額數(shù)，這樣，可以保證：當我們計算金額i的硬幣組合數(shù)dp[i]時，前面更少的金額的組合數(shù)比如dp[i-1]、dp[i-2]······等都已求出。

• 那么，對任意的dp[i]，面對某種硬幣的面額（記為coin），如果在湊成金額i時選擇了這枚硬幣，那么它也包含了湊成金額（i-coin）時的組合個數(shù)。而對不同面值的硬幣coin，都需要累加所有的組合個數(shù)。

class?Solution(object):
????def?change(self,?amount,?coins):
????????"""
????????:type?amount:?int
????????:type?coins:?List[int]
????????:rtype:?int
????????"""

????????dp?=?[0]*(amount+1)
????????dp[0]?=?1

????????for?coin?in?coins:
????????????sum_coin?=?coin
????????????
????????????while?sum_coin?<=?amount:
????????????????dp[sum_coin]?+=?dp[sum_coin-coin]
????????????????sum_coin?+=?1
????????
????????return?dp[amount]