mycode
我开始错误的思路：先用大钱除总钱数来保证 fewest number of coins，当最后剩下的amount小于最小币值的货币时，就说明return -1，但是这样想是有问题的！！！
例如：[1,4,5] 12=5*2+2 12 =5*2 + 1*2 用了4枚，但是12 = 4*3
因为还有下一步，也就是用次大的币值去重复这个步骤！！而且也不能直接去使用次大的，而是先把最大币值的数目-1，-2，-3.。。。依次看
参考：
思路:类似于上一个62.unique paths，就要要考虑能到达该点的路径中的上一个点的情况
class Solution(object): def coinChange(self, coins, amount): """ :type coins: List[int] :type amount: int :rtype: int """ n = len(coins) # dp[i]表示amount=i需要的最少coin数 dp = [float("inf")] * (amount+1) dp[0] = 0 for i in range(amount+1): for j in range(n): # 只有当硬币面额不大于要求面额数时，才能取该硬币 if coins[j] <= i: dp[i] = min(dp[i], dp[i-coins[j]]+1) # 硬币数不会超过要求总面额数，如果超过，说明没有方案可凑到目标值 return dp[amount] if dp[amount] <= amount else -1
leetcode-mid-dynamic programming-322. Coin Change - NO
原文：https://www.cnblogs.com/rosyYY/p/10978958.html