算法刷题

322. 零钱兑换
给你一个整数数组 coins ，表示不同面额的硬币；以及一个整数 amount ，表示总金额。
计算并返回可以凑成总金额所需的 最少的硬币个数 。如果没有任何一种硬币组合能组成总金额，返回 -1 。
你可以认为每种硬币的数量是无限的。
示例 1：
输入：coins = [1, 2, 5], amount = 11
输出：3 
解释：11 = 5 + 5 + 1
示例 2：
输入：coins = [2], amount = 3
输出：-1
示例 3：
输入：coins = [1], amount = 0
输出：0

DFS 搜索树太深直接超时

python
from typing import List
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        coins.sort(reverse=True)
        self.coins_num_res = float("inf")
        def dfs(start, coins_num, residue):
            if residue == 0:
                self.coins_num_res = min(self.coins_num_res, coins_num)
                return
            for index in range(start, len(coins)):
                dfs(index + 1, coins_num, residue)  # dfs 路径1， 不选当前的硬币
                if coins[index] > residue:  # 当前的硬币选了后钱会多，剪枝
                    continue
                # 剪枝，coins_num_res 有结果。
                # 剪枝了也会超时
                if self.coins_num_res != float("inf") and (self.coins_num_res - coins_num) * coins[start] < residue:
                    break
                dfs(index, coins_num + 1, residue - coins[index])  # # dfs 路径2， 选上当前的硬币
        dfs(0, 0, amount)
        return self.coins_num_res if self.coins_num_res != float("inf") else -1
print(Solution().coinChange([1, 2, 5], 11))
# print(Solution().coinChange([411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422], 9864))

BFS 最快的

构建BFS搜索必然借助deque，但是deque里面装什么，怎么搜，始终不太好想象：

python
from typing import List
class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        from collections import deque
        queue = deque([amount])
        step = 0
        visited = set()
        while queue:
            n = len(queue)
            for _ in range(n):  # 本轮选择硬币
                residue = queue.pop()
                if residue == 0:
                    return step
                for coin in coins:
                    # residue >= coin 是停止条件
                    # (residue - coin) not in visited 是剪枝
                    if residue >= coin and (residue - coin) not in visited:
                        visited.add(residue - coin)
                        queue.appendleft(residue - coin)
            step += 1
        return -1
print(Solution().coinChange([411, 412, 413, 414, 415, 416, 417, 418, 419, 420, 421, 422], 9864)) # 3万多次循环

动态规划

python
class Solution1:
    def coinChange(self, coins: List[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
        for coin in coins:
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1