leetcode-go/动态规划/85-零钱兑换.md

tags, create time

tags	create time
算法/动态规划 完全背包 基础DP	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，你一定会拿起最后一枚硬币。枚枚举这枚硬币是什么，剩下交给子问题。

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 ← 答案

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（推荐 ✅）

// 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：枚举"最后一枚硬币可能是哪个"，从多个可能的前驱状态中选最小值
• 空间顺序：先金额后硬币（也可以反过来，因为是完全背包，两种遍历顺序都正确）

版本二：精简写法

// 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)，属于典型的完全背包最小化问题