零钱兑换Python解法_给你一个整数数组coins,表示不同面额的硬币,以及一个整数amount,表示总金额。

给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。

计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。

你可以认为每种硬币的数量是无限的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/coin-change
 

例：

输入：coins = [1, 2, 5], amount =11

输出：3
 
解释：11 = 5 + 5 + 1

# 解析：动态规划，从总金额1开始遍历，若当前金额大于数组中正在判断的金额，那么减去硬币的值得到的值可以在前面的金额中找到，若找不到即为-1，找到了则加上这枚硬币即可（硬币数目加一），每个硬币都判断完后，符合要求的情况再求出硬币最少的情况。

class Solution(object):
    def coinChange(self, coins, amount):
        """
        :type coins: List[int]
        :type amount: int
        :rtype: int
        """
        res = [0 for i in range(amount + 1)]  # 初始化为0，因为下标的原因多一位
 
        for i in range(1, amount+1):  # 对目标金额以及小于它的所有金额进行遍历
            cost = float('inf')  # 消耗数目初始化为无穷大，因为要找最小值
            for c in coins:  # 对数组中的硬币进行判断
                if i - c >= 0:  # 如果当前值大于硬币值，那么减去可获得之前的金额数
                    cost = min(cost, res[i - c] + 1)  # 在之前的金额数上加一然后与之前的消耗数目比较，选出数目最小的那种情况
            res[i] = cost  # 然后将最少的情况放入dp数组
        
        if res[amount] == float('inf'):  # 判断，如果dp数组的目标金额存放位置为无穷大（inf）说明没有可以实现的情况
            return -1  # 返回-1
        else:
            return res[amount]  # 存在直接返回数值即可