零錢兌換
題目
給定不同面額的硬币 coins 和一個總金額 amount。編寫一個函數來計算可以湊成總金額所需的最少的硬币個數。如果沒有任何一種硬币組合能組成總金額，傳回 -1。
示例 1:
輸入: coins = [1, 2, 5], amount = 11
輸出: 3
解釋: 11 = 5 + 5 + 1
示例 2:
輸入: coins = [2], amount = 3
輸出: -1
說明:
你可以認為每種硬币的數量是無限的。
解題思路
貪心算法 + DFS；
在本題當中，可以考慮先取最大面值的硬币（先對 coins 進行排序，由大到小），當取最大面值的硬币超出總額的時候，則取下一個稍微小的硬币；
當取硬币的時候，不一定要逐個取，用乘法代替加法。比如：times = amout // coins[index]，這個式子就是計算最多可取多少個硬币。這裡可能取到一種情況，就是由大到小取硬币的時候，可能前面的取的硬币導緻後面無法湊出總額。遇到這種情況則考慮回溯減少前面取較大硬币的數量。
這裡要考慮一些特殊的情況。coins = [1, 7, 10]， amount = 14，按照上面的思路，這裡優先得到的結果可能是 10, 1, 1, 1, 1，而不是最優的 7, 7，是以要将所有的情況遞歸完成。
上面的問題可以看出，貪心算法可能得到的不是最優解，但同樣可以實作快速剪枝。
代碼實作
class Solution:
def coinChange(self, coins: List[int], amount: int) -> int:
def coin_change(coins, amount, index, count, res):
if amount == 0:
return min(count, res)
if index == len(coins):
return res
# 這裡用乘法代替加法，直接獲得最多可取值
times = amount // coins[index]
while times >= 0 and count + times < res:
res = coin_change(coins, amount - times * coins[index], index + 1, count + times, res)
times -= 1
return res
if amount == 0:
return 0
coins.sort(reverse=True)
res = coin_change(coins, amount, 0, 0, float('inf'))
return res if res != float('inf') else -1
實作結果
以上就是使用貪心算法 + DFS 解決《零錢兌換》問題的主要内容。
歡迎關注微信公衆号《書所集錄》