322. 零钱兑换

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

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

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

示例 1：

1 2 3

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

示例 2：

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

示例 3：

1 2	>输入：coins = [1], amount = 0 >输出：0

这道题目和完全平方数一样也是完全背包问题，唯一的区别就是考虑一下边界问题以及什么时候返回空值

由于我们只需要考虑最后一位，如果dp数组中最后一位无法通过物品凑得，那么它的值就不会改变（和初始值一样）这样只需要判断最后得到的是否为初始值即可知道能否成功兑换

代码：

1
2
3
4
5
6
7
8
9
10
11
12

class Solution(object):
    def coinChange(self, coins, amount):
        dp = [10**4+1]*(amount + 1)
        dp[0] = 0
        # 遍历背包
        for j in range(1, amount + 1):
            # 遍历物品
            for num in coins:
                if j >= num:
                    dp[j] = min(dp[j], dp[j - num] + 1)
        if dp[-1] == 10**4+1:return -1
        return dp[amount]