题目来源：https://leetcode-cn.com/problems/coin-change/
题目给定不同面额的硬币 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 解决《零钱兑换》问题的主要内容。
