---
tags: [算法/动态规划, 完全背包, 基础DP]
create time: 2026-05-16 19:00
---

# 322. 零钱兑换（Coin Change）

> [!quote] LeetCode 原题 · 中等
> 给你一个整数数组 `coins`，表示不同面额的硬币；以及一个整数 `amount`，表示总金额。
>
> 计算并返回可以凑成总金额所需的 **最少的硬币个数**。如果没有任何一种硬币组合能组成总金额，返回 -1 。
>
> 你可以认为每种硬币的数量是无限的。
>
> - 输入范围：`1 <= coins.length <= 12`，`1 <= coins[i] <= 2³¹ - 1`，`0 <= amount <= 10⁴`

## 题面

**示例 1：**

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

**示例 2：**

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

**示例 3：**

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

## 思路

### 第一步：识别问题模型

> [!question] 💡 思考
> 题目说"每种硬币数量无限"，目标是"最少硬币数凑出 amount"——这和之前哪道题的内核一致？

没错！**[[84-完全平方数]]** 和这道题的本质一模一样：都是给定一组"面额"，每种可以无限取用，要求凑出目标值的最小件数。

我们可以把它看作一道**「最小物品数」版本的完全背包**：

| DP 要素 | 含义 |
|---------|------|
| **物品集合** | 所有硬币面额 coins[0..m-1] |
| **背包容量** | amount |
| **每种物品数量** | 无限 |
| **价值定义** | 每件物品的"代价"为 1（一枚硬币算一次） |
| **优化目标** | 总代价最小 |

### 第二步：定义状态与转移方程

定义状态：

> `dp[i]` = 凑出金额 i 所需的最少硬币个数

那状态怎么转移？考虑"最后一步拿的是哪枚硬币"——假设最后拿的是 `coins[j]`，那么之前的金额就是 `i - coins[j]`，需要的硬币数是 `dp[i - coins[j]]`。所以：

> **`dp[i] = min(dp[i - coins[j]]) + 1`**，对所有满足 `coins[j] ≤ i` 的 j 取最小值

核心直觉很简单：

> 要凑到金额 i，你一定会拿起最后一枚硬币。枚枚举这枚硬币是什么，剩下交给子问题。

```mermaid
flowchart TD
    subgraph "dp[11] 的状态转移 (coins=[1,2,5])"
        A["dp[11]\n= min(...) + 1"] --> B["最后拿 1:\ndp[10] + 1"]
        A --> C["最后拿 2:\ndp[9] + 1"]
        A --> D["最后拿 5:\ndp[6] + 1"]
        B --> E["dp[10]=2 → ans=3"]
        C --> F["dp[9]=2 → ans=3"]
        D --> G["dp[6]=2 → ans=3 ✓"]
    end

    style A fill:#e7f3ff,stroke:#3b82f6
    style E fill:#dcfce7,stroke:#16a34a
    style F fill:#dcfce7,stroke:#16a34a
    style G fill:#dcfce7,stroke:#16a34a
```

> [!note] 📝 为什么这是正确的？
> 因为"完全背包"有一个关键性质：**最优子结构**。凑出金额 i 的最优方案中，去掉最后一枚硬币后，剩余部分一定也是对应金额的最优方案。否则我们可以用更优的子方案替换它，得到更好的整体解——矛盾。

### 第三步：确定边界条件

| 情况 | dp 值 | 理由 |
|------|-------|------|
| `dp[0]` | **0** | 凑出金额 0 不需要任何硬币，这是递推的"空起点" |
| 其他 `dp[i]` | **+∞（不可达）** | 初始化为无穷大，表示还未找到可行方案 |

> [!warning] ⚠️ 注意"不可达"的处理
> 如果最终 `dp[amount]` 仍然是无穷大，说明无法凑出该金额，应返回 **-1**。例如 coins = [2], amount = 3 时，dp[3] 永远不会被更新。

### 第四步：自底向上填表

以 `coins = [1, 2, 5], amount = 11` 为例：

| i | dp[i] 计算过程 | dp[i] |
|---|--------------|-------|
| 0 | — | **0** |
| 1 | min(dp[0]+1) | **1** |
| 2 | min(dp[1]+1, dp[0]+1) | **1** |
| 3 | min(dp[2]+1, dp[1]+1) | **2** |
| 4 | min(dp[3]+1, dp[2]+1, dp[-1]无效) | **2** |
| 5 | min(dp[4]+1, dp[3]+1, dp[0]+1) | **1** ← 正好有面额 5！ |
| 6 | min(dp[5]+1, dp[4]+1, dp[1]+1) | **2** |
| 7 | min(dp[6]+1, dp[5]+1, dp[2]+1) | **2** |
| 8 | min(dp[7]+1, dp[6]+1, dp[3]+1) | **3** |
| 9 | min(dp[8]+1, dp[7]+1, dp[4]+1) | **3** |
| 10 | min(dp[9]+1, dp[8]+1, dp[5]+1) | **2** |
| 11 | min(dp[10]+1, dp[9]+1, dp[6]+1) | **3** ← 答案 |

```mermaid
flowchart LR
    subgraph "填表示意"
        A["dp[0]=0"] --> B["dp[1]=1"]
        B --> C["dp[2]=1"]
        C --> D["dp[3]=2"]
        D --> E["dp[4]=2"]
        E --> F["dp[5]=1 ★"]
        F --> G["dp[6]=2"]
        G --> H["dp[7]=2"]
        H --> I["dp[8]=3"]
        I --> J["dp[9]=3"]
        J --> K["dp[10]=2"]
        K --> L["dp[11]=3\n★答案"]
    end

    style A fill:#f3f4f6,stroke:#6b7280
    style F fill:#fef3c7,stroke:#f59e0b
    style L fill:#dcfce7,stroke:#16a34a
```

> 表中 ★ 标记表示可以直接用一枚硬币凑出（amount 本身在硬币列表中）。

## 代码提示

在动手写代码之前，想一想这些关键决策点：

> [!question] 💡 思考 1
> Go 语言中没有"无穷大"常量——你会用什么值来表示不可达？

可以用 `amount + 1`：因为最多只需要 amount 个 1 元硬币就能凑出任意 amount，所以 **超过 amount 的硬币数一定是无意义的**。这个巧妙的设计让判断"是否可达"变得非常简单——只需检查 `dp[amount] > amount`。

> [!question] 💡 思考 2
> 内层循环中，如何避免负索引越界？

对每个硬币 `coin`，只有当 `i >= coin` 时才考虑从 `dp[i-coin]` 转移。这样天然避免了索引问题。

## 技巧

### "无穷大"的巧妙取值

> [!tip] ⚡ 小技巧：为什么选 amount+1 作为无穷大？
>
> 如果全部使用 1 元硬币，凑出 amount 需要恰好 amount 枚。**任何合理的方案都不会超过这个数字**。因此：
> - `dp[i] > amount` → 说明没有找到可行方案（不可达）
> - `dp[i] <= amount` → 这就是真正的最优解

这样既避免了引入额外常量，又简化了最终结果的判断逻辑。

### BFS 替代方案

> [!abstract] 🔍 进阶视角：BFS 求最短路径
>
> 另一种等价的建模方式是把金额看作节点、把每次加一枚硬币看作边。从 amount 开始做 BFS，第一次到达 0 时的层数就是答案。
>
> - **优势**：BFS 天然保证第一层到达的就是最优解，无需全部填完表格
> - **劣势**：最坏空间复杂度 O(amount)，不如 DP 稳定
>
> 面试中推荐 DP 解法，但知道 BFS 思路可以增加灵活性。

### 剪枝优化

> [!tip] ⚡ 小优化：先排序硬币
>
> 将硬币按面额从大到小排序后，内层循环可以先尝试大面额硬币。虽然不影响渐近时间复杂度，但在实际测试数据中往往能更快找到较优的中间解，减少后续比较的次数。

| 方法 | 时间 | 空间 | 评价 |
|------|------|------|------|
| DP 填表（推荐） | O(amount × m) | O(amount) | 直观通用，面试首选 |
| BFS | O(amount × m) | O(amount) | 第一层到达即最优，略快 |
| 带记忆化的 DFS | O(amount × m) | O(amount) | 递归写法，代码简洁但有栈溢出风险 |

其中 m = coins.length。

## 代码

### Go 语言实现

#### 版本一：自底向上 DP（推荐 ✅）

```go
// coinChange returns the minimum number of coins to make up the given amount.
// If it's impossible, returns -1.
func coinChange(coins []int, amount int) int {
	// maxCoins 充当"无穷大"：最多只用 amount 个 1 元硬币
	maxCoins := amount + 1

	// dp[i] = 凑出金额 i 所需的最少硬币个数
	dp := make([]int, amount+1)

	// 初始化：全部设为"不可达"
	for i := 1; i <= amount; i++ {
		dp[i] = maxCoins
	}
	// 边界：凑出金额 0 不需要硬币
	dp[0] = 0

	// 自底向上填表：先枚举金额，再枚举硬币
	for i := 1; i <= amount; i++ {
		for _, coin := range coins {
			if i < coin {
				continue // 当前硬币面额大于目标金额，跳过
			}
			// 选或不选这枚硬币：dp[i] = min(不用这枚, 用这枚 + 1)
			used := dp[i-coin] + 1
			if used < dp[i] {
				dp[i] = used
			}
		}
	}

	// 如果 dp[amount] 仍为无穷大，说明无法凑出
	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}
```

> [!summary] 💡 代码结构拆解
> - **外层 for i**：从左到右依次计算 dp[1]...dp[amount]，确保每个子问题在用到时已解决
> - **内层 for coin**：枚举"最后一枚硬币可能是哪个"，从多个可能的前驱状态中选最小值
> - **空间顺序**：先金额后硬币（也可以反过来，因为是完全背包，两种遍历顺序都正确）

#### 版本二：精简写法

```go
// coinChange returns the minimum number of coins to make up the given amount.
// Space and code simplified version.
func coinChange(coins []int, amount int) int {
	dp := make([]int, amount+1)

	// Go 的 slice 零值初始化为 0，恰好 dp[0]=0 符合预期
	// 其余位置需要手动标记为"不可达"
	for i := range dp {
		if i > 0 {
			dp[i] = amount + 1
		}
	}

	for i := 1; i <= amount; i++ {
		for _, c := range coins {
			if i >= c {
				v := dp[i-c] + 1
				if v < dp[i] {
					dp[i] = v
				}
			}
		}
	}

	if dp[amount] > amount {
		return -1
	}
	return dp[amount]
}
```

### 执行过程演示（coins = [1, 2, 5], amount = 11）

```
初始: dp[0]=0, 其余均为 ∞(=12)

i=1: coin=1: dp[0]+1=1   → dp[1]=1
i=2: coin=1: dp[1]+1=2   → dp[2]=2
     coin=2: dp[0]+1=1   → dp[2]=1 ★更新
i=3: coin=1: dp[2]+1=2   → dp[3]=2
     coin=2: dp[1]+1=2   → 不更新(相等)
i=4: coin=1: dp[3]+1=3   → dp[4]=3
     coin=2: dp[2]+1=2   → dp[4]=2 ★更新
i=5: coin=1: dp[4]+1=3   → dp[5]=3
     coin=2: dp[3]+1=3   → 不更新
     coin=5: dp[0]+1=1   → dp[5]=1 ★更新(正好面额5!)
i=6: coin=5: dp[1]+1=2   → dp[6]=2
...（以此类推）...
i=10: coin=5: dp[5]+1=2  → dp[10]=2
i=11: coin=5: dp[6]+1=3  → dp[11]=3

结果: dp[11] = 3 ✅ (11 = 5+5+1)
```

### 复杂度分析

- **时间复杂度：O(amount × m)** — 外层循环 amount 次，内层循环 m 次（m 为硬币种类数），每次只做常数次操作。代入题目约束：最多 10⁴ × 12 = 1.2 × 10⁵ 次操作
- **空间复杂度：O(amount)** — dp 数组占用 amount+1 个整型空间

## 举一反三

这道题是 **"完全背包"** 思想的第一道落地应用，也是 DP 入门必刷的经典：

- [[84-完全平方数]] — 本质相同的"最小件数"问题，只是面额集合换成完全平方数
- [[83-打家劫舍]] — 同样是逐状态递推，但约束是"不相邻"而非"无限选取"
- LeetCode 279. 完全平方数 — 同上一题
- LeetCode 518. 零钱兑换 II —— **变种**：改为求"组合数"而非"最少个数"，转移方程变为累加而非取 min
- LeetCode 377. 组合总和 Ⅳ —— **变种**：排列数和组合数的区别（外层枚举目标和 vs 外层枚举物品）

> [!summary] 📌 本节要点
> 1. 定义 dp[i] = 凑出金额 i 的最少硬币个数
> 2. 状态转移：dp[i] = min(dp[i - coin]) + 1，枚举每枚可能的最后硬币
> 3. 边界 dp[0] = 0，初始化 dp[i] = amount + 1（表示不可达）
> 4. 最终判断：若 dp[amount] > amount 则返回 -1
> 5. 复杂度 O(amount × m)，属于典型的完全背包最小化问题