【DP、BFS】322. Coin Change

问题描述：

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:

Input: coins = [1, 2, 5], amount = 11
Output: 3 
Explanation: 11 = 5 + 5 + 1

Example 2:

Input: coins = [2], amount = 3
Output: -1

Note:

• You may assume that you have an infinite number of each kind of coin.

解题思路：

刚开始想的是能不能像 【DP、Greedy】416. Partition Equal Subset Sum 这道题那样，硬币从大到小排序，然后使用贪心算法来求解。但是如果几个例子，比如 coins = [4,3],，amount = 14，如果使用贪心，会找到 4 4 4，然后发现到不了 14，返回 -1。实际上，应该是 4 4 3 3，返回 4。因此，贪心的思想行不通。

方法1：动态规划（DP）

这道题首先就会想到用完全背包的思想来求解。参考之前写的文章： 01-背包、完全背包、多重背包及其相关应用。

• 硬币对应完全背包问题中的物品重量，amount 对应背包容量，最少的硬币数对应背包最大价值。因此，我们只需要创建一个大小为 dp[amount+1] 的数组，dp[j] 表示兑换 j 块钱所需要的最少硬币数。
• 因为要更新这个 dp 数组来求最少硬币数，所以除了 dp[0] = 0 外，其它位置都应该初始化为 float("inf")。
• 外层循环是对 coins 的遍历，即 for coin in coins，内层循环 j 的状态转移方程只需要将完全背包中的 dp[j] = max(dp[j], dp[j-w[i]] + v[i]) 对应替换为 dp[j] = min(dp[j], dp[j-coin] + 1) 即可。
• 如果最后 dp[-1] == float("inf")，说明不能兑换 amount，应该返回 -1，否则，dp[-1] 就是最后的答案。

Python3 实现：

class Solution:
    # 方法1：DP, 完全背包
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [0] + [float("inf")] * amount
        for coin in coins:
            for j in range(coin, amount+1):  # 从 coin 开始递增到 amount
                dp[j] = min(dp[j], dp[j-coin] + 1)
        if dp[-1] == float("inf"):
            return -1
        else:
            return dp[-1]

print(Solution().coinChange([4,3], 14))  # 4

方法2：广度优先搜索（BFS）

这道题和这样的题目很类似：一个人要从原点 0 走到 amount，每一次有不同走法，求走到 amount 所需要的最少步数。而之前写过这样的题目的做法：从M走到N最少步数。

对于这道题目，硬币种类数对应不同的走法，最少的硬币数对应最少步数。因此，我们可以使用 BFS 方法求解。

注意：这道题和 从M走到N最少步数 的区别在于，找硬币问题的 amount 不一定可达。在编程时，如果在某一层中，所有的数如果都大于 amount，说明肯定到达不了 amount 了，因为往下找只会越来越大。 因此，我们可以用一个标记变量标记是否所有的数都大于 amount，从而判断要不要继续向下找下去。

Python3 实现：

class Solution:
    # 方法2：BFS
    def coinChange(self, coins: List[int], amount: int) -> int:
        visited = [True] + [False] * amount
        dis = [(0,0)]
        minl = 0  # 层数就是最少硬币数
        while True:
            if visited[amount] == True:  # 能够组合成功的出口
                return minl
            flag = False  # 标记要不要继续找下去
            while len(dis) > 0 and dis[0][1] == minl:  # 来自相同的层数
                tem = dis.pop(0)  # 按照队列形式，从头开始取
                if tem[0] < amount:
                    flag = True
                for coin in coins:
                    if tem[0]+coin <= amount and visited[tem[0]+coin] == False:  # 注意下标可能越界问题
                        dis.append((tem[0]+coin, minl+1))
                        visited[tem[0]+coin] = True
            if flag == False:  # 当前层所有数字都比 amount 大，说明不可能组合成功
                return -1
            minl += 1
        return -1  # 实际上不会执行这句话，因为这棵树是无穷尽的

print(Solution().coinChange([1,2,5], 11)) # 3