ChangeExchangeTopic来源：https://leetcode-cn.com/problems/coin-change/题目给出了不同面额的硬币和总金额。编写一个函数来计算最少需要多少个硬币来弥补总量。如果没有硬币组合构成总数，则返回-1。示例1：输入：coins=[1,2,5],amount=11输出：3解释：11=5+5+1示例2：输入：coins=[2],amount=3输出：-1解释：您可以认为每个硬币的数量是无限的。解题思路贪心算法+DFS；在这道题中，可以考虑先拿面额最大的硬币（先把硬币排序，从大到小排序），当面额最大的硬币超过总量时，拿一枚稍小的硬币；拿硬币时，不必一枚一枚地拿，要用乘法代替加法。例如：times=amout//coins[index]，这个公式就是计算最多可以提取的coin数量。这里可能会出现一种情况，就是在从大到小取币的时候，前面取的币可能导致后面无法补齐总量。在这种情况下，请考虑回溯以减少较早获得的较大硬币的数量。这里有一些特殊情况需要考虑。coins=[1,7,10],amount=14，按照上面的思路，这里的首选结果可能是10,1,1,1,1，而不是最优的7,7，所以所有的case递归完成.从以上问题可以看出，贪心算法不一定能得到最优解，但也能实现快速剪枝。代码实现类解决方案：defcoinChange(self,coins:List[int],amount:int)->int:defcoin_change(coins,amount,index,count,res):ifamount==0:returnmin(count,res)ifindex==len(coins):returnres#这里用乘法代替加法直接得到最大可能值times=amount//coins[index]whiletimes>=0andcount+times
