题目

难度：★★★☆☆
类型：数组
方法：动态规划

传送门

给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。

示例

示例 1:

输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1

示例 2:

输入: coins = [2], amount = 3
输出: -1

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

解答

这是一个典型的完全背包问题。

设置dp数组，维度为m+1，dp[i]表示金额i需要的最少硬币数，
初始状态：这里增加的1，主要是要考虑总金额为0的情况，这种情况的组合方式为零，因此需要设置dp[0]=0，其他位置填充无穷大。

状态转移：金额从小到大遍历，我们取得一种硬币c，可以更新dp数组中所有超过该金额面值的部分，例如4元可以用4个1元组成，现在就可以用两个2元组成。
状态转移方程是：dp[i] = min(dp[i], dp[i-c]+1)，这里的dp[i-c]是组成i-c金额所需最小硬币数，那么dp[i-c]+1中的+1表示的就是使用该硬币c取代原始方式。
因为不一定这样的方案会让所使用硬币数量更少，所以需要和当前状态进行比较并取最小值，这也是为什么一开始要设置inf的原因。

返回值：当dp[m]为inf时，相当于没有一种组合方式可以完成，因此返回-1，否则返回dp[m]

关于用动态规划解决01背包问题，完全背包问题和多重背包问题，推荐参考大佬的总结

class Solution:
    def coinChange(self, coins, m):
        dp = [0] + [float('inf')] * m
        for c in coins:                                 # 枚举硬币种数
            for j in range(c, m+1):                     # 从小到大枚举金额
                dp[j] = min(dp[j], dp[j - c] + 1)
        return -1 if dp[m] == float('inf') else dp[m]     # 如果为inf说明状态不可达，返回-1即可。

如有疑问或建议，欢迎评论区留言~