322. 零钱兑换

题目链接（中等）

题目描述

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

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

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

数据范围：

• 1 <= coins.length <= 12
• 1 <= coins[i] <= 2^31 - 1
• 0 <= amount <= 10^4

示例

示例 1：

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

示例 2：

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

示例 3：

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

核心思路

问题本质：用面额数组 coins 中的硬币（每种可取无限次）凑出总金额 amount，求所需的最少硬币数。

转化为完全背包：

• 物品：每种硬币面额；
• 容量：总金额 amount；
• 目标：装满容量所需的最少物品数（每个物品可取无限次）；
• 价值：每枚硬币价值 1（求最少数量，即求最小价值）。

两种主流解法：

1. 记忆化搜索：自顶向下，用递归 + 缓存消除重复子问题；
2. 动态规划（自底向上）：dp[i] 表示凑出金额 i 的最少硬币数，标准完全背包。

---

方法一：记忆化搜索（自顶向下）

思路及解法

定义 dp(rem) = 「凑出剩余金额 rem 所需的最少硬币数」。

递归思路：

• 若 rem < 0：金额无法凑出，返回 -1；
• 若 rem == 0：不需要硬币，返回 0；
• 否则，枚举每个硬币面额 coin，递归求 dp(rem - coin)：
  • 若 dp(rem - coin) >= 0（子问题有解），更新最小值为 dp(rem - coin) + 1；
• 若所有子问题都无解，返回 -1。

用 lru_cache 记忆化：dp(rem) 只依赖 rem，可以用缓存避免重复计算。这样每个 rem 只算一次。

直觉理解：想凑出 rem，最后一枚硬币可能是 coins 中的任意一种，枚举「最后一枚」，问题就缩小了。

代码

from functools import lru_cache

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        @lru_cache(maxsize=None)
        def dp(rem: int) -> int:
            if rem < 0:
                return -1
            if rem == 0:
                return 0

            best = float('inf')
            for coin in coins:
                res = dp(rem - coin)
                if res >= 0 and res + 1 < best:
                    best = res + 1

            return best if best != float('inf') else -1

        return dp(amount)

复杂度分析

• 时间复杂度：$O(S \cdot n)$，共 $S + 1$ 个状态，每个状态枚举 $n$ 种硬币。
• 空间复杂度：$O(S)$，缓存加上递归栈。

---

方法二：动态规划（自底向上，推荐）

思路及解法

定义 dp[i] = 「凑出金额 i 所需的最少硬币数」。

转移方程：

$$dp[i] = \min_{c \in coins,\ c \le i} dp[i - c] + 1$$

即：枚举最后一枚硬币面额 c，从金额 i - c 的状态转移过来，再加上这枚硬币。

边界：

• dp[0] = 0（凑出金额 0 不需要硬币）；
• 其余初始化为一个「不可能的大数」（比如 float('inf')），表示暂时无法凑出。

遍历顺序：

• 外层枚举硬币，内层正序枚举金额（完全背包的标准写法）；
• 内层正序：每个硬币可以重复使用；
• 也可以外层枚举金额，内层枚举硬币，效果相同。

答案：dp[amount]，若仍为 inf 则返回 -1。

举例：coins = [1, 2, 5]，amount = 11

金额 i	dp[i]	说明
0	0	边界
1	1	1
2	1	2
3	2	2 + 1
4	2	2 + 2
5	1	5
…	…	…
11	3	5 + 5 + 1

代码

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0

        for coin in coins:
            for i in range(coin, amount + 1):
                dp[i] = min(dp[i], dp[i - coin] + 1)

        return dp[amount] if dp[amount] != float('inf') else -1

另一种写法：外层枚举金额，内层枚举硬币：

for i in range(1, amount + 1):
    for coin in coins:
        if i >= coin:
            dp[i] = min(dp[i], dp[i - coin] + 1)

两种写法等价，都正确。

复杂度分析

• 时间复杂度：$O(S \cdot n)$，共 $S$ 个状态，每个状态枚举 $n$ 种硬币。
• 空间复杂度：$O(S)$，dp 数组长度为 S + 1。

---

方法三：BFS（从 0 到 amount 的最短路径）

思路及解法

把问题看成一张图：

• 节点：金额 0 到 amount；
• 边：从金额 x 出发，可以选择一枚硬币 c，到达金额 x + c；
• 目标：求从 0 到 amount 的最短路径长度（即最少硬币数）。

用 BFS 逐层扩展：

1. 初始队列 [0]，步数 step = 0；
2. 每轮把当前队列中的节点全部弹出，对每个节点加上每种硬币面额，得到新金额；
3. 若新金额等于 amount，返回 step + 1；
4. 若新金额在范围内且未被访问，加入队列，标记已访问；
5. 队列为空仍未到达，返回 -1。

用 visited 去重：同一个金额只需入队一次，否则会重复扩展。

代码

from collections import deque

class Solution:
    def coinChange(self, coins: list[int], amount: int) -> int:
        if amount == 0:
            return 0

        visited = [False] * (amount + 1)
        visited[0] = True
        q = deque([0])
        step = 0

        while q:
            step += 1
            for _ in range(len(q)):
                x = q.popleft()
                for coin in coins:
                    nxt = x + coin
                    if nxt == amount:
                        return step
                    if nxt < amount and not visited[nxt]:
                        visited[nxt] = True
                        q.append(nxt)

        return -1

复杂度分析

• 时间复杂度：$O(S \cdot n)$，每个金额最多入队一次，每次枚举 $n$ 种硬币。
• 空间复杂度：$O(S)$，队列和 visited 数组。

---

三种方法对比

方法	时间	空间	特点
记忆化搜索	$O(Sn)$	$O(S)$	自顶向下，思路直观
DP（自底向上）	$O(Sn)$	$O(S)$	标准完全背包，面试首选
BFS	$O(Sn)$	$O(S)$	求最短路径的视角，代码稍长

推荐：

• 面试：首选 DP，思路清晰、模板通用；
• 开场思路：可以先讲记忆化搜索（递归更好想），再优化到 DP；
• 加分：能讲 BFS 的图论视角，展示思维广度。

---

关键细节

1. 与 0-1 背包的区别

	0-1 背包	完全背包
每个物品	最多取一次	可取无限次
内层容量遍历方向	倒序	正序

本题每个硬币可以重复使用，所以内层遍历是正序。

2. 为什么用 float('inf') 作初始值

• 表示「暂时无法凑出」；
• 用 min 更新时，inf 不会干扰结果；
• 最终若仍为 inf，说明无法凑出，返回 -1。

3. 完全背包的两种枚举顺序

• 外层硬币，内层金额：更容易理解「每个硬币可以重复使用」；
• 外层金额，内层硬币：更符合「状态转移」的直觉。

两种都正确，因为是完全背包的组合数问题（不在乎硬币的顺序），所以枚举顺序无所谓。

4. 记忆化搜索和 DP 的关系

• 记忆化搜索：自顶向下，递归写法，lru_cache 自动缓存；
• DP：自底向上，填表写法。

两者本质相同，都是「状态 + 转移」。

5. BFS 的图论视角

本题的 BFS 解法把问题转化为「从 0 到 amount 的最短路径」，与「单词接龙」等题类似。

需要注意：

• 每个金额只入队一次（用 visited 标记）；
• 每层代表一步，步数即硬币数。

6. 一个易错点

判断 dp[amount] 是否可达：

return dp[amount] if dp[amount] != float('inf') else -1

不能直接返回 dp[amount]，因为无解时它是 inf，题目要求返回 -1。

---

总结

• 状态定义：dp[i] = 凑出金额 i 的最少硬币数；
• 转移方程：dp[i] = min(dp[i - c] + 1)，c ∈ coins；
• 边界：dp[0] = 0，其余为 inf；
• 遍历顺序：外层硬币、内层正序（完全背包）；
• 答案：dp[amount]，若为 inf 则返回 -1；
• 本质：完全背包的「最少物品数」版本；
• 通用套路：「凑金额 / 凑容量」 + 「元素可重复」 → 完全背包。

相关题目

• LC 279. 完全平方数（完全背包）
• LC 518. 零钱兑换 II（完全背包，求方案数）
• LC 377. 组合总和 IV（完全背包，排列数）
• LC 416. 分割等和子集（0-1 背包）
• LC 494. 目标和（0-1 背包）