从能算到秒杀：零钱兑换与「最少硬币」的数学真相
如果说279. 完全平方数 是在考你：
👉最少用几个平方数拼出一个数
那322. 零钱兑换 就是它的「现实版」：
👉最少用几枚硬币凑出一个金额
这也是我第一次真正明白一句话：
所有「最少数量」的问题，本质都是最短路径。
🟢 题目速览
LeetCode 322. 零钱兑换（中等）
给你一个整数数组coins，表示不同面额的硬币；
再给你一个整数amount，表示总金额。
请你计算：凑出 amount 所需的最少硬币个数。
每种硬币无限使用
如果无法凑出，返回
-1
示例
输入：coins = [1,2,5], amount = 11 输出：3 解释：11 = 5 + 5 + 1输入：coins = [2], amount = 3 输出：-1🧠 我的第一反应（很真实）
看到「最少数量」，大脑自动弹出三个词：
BFS？
DP？
背包问题？
于是立刻写出：
dp[i] = min(dp[i - coin] + 1)✅ 对
❌ 但不够
因为这题真正的坑在于：
amount 很大
coins 很小
不能只靠直觉
🚀 解法一：BFS（最直观）
把问题看成一张图：
节点：金额
0 ~ amount边：减去一枚硬币
目标：从
0 → amount的最少步数
class Solution { public int coinChange(int[] coins, int amount) { Queue<Integer> queue = new LinkedList<>(); boolean[] visited = new boolean[amount + 1]; queue.offer(0); visited[0] = true; int steps = 0; while (!queue.isEmpty()) { int size = queue.size(); for (int i = 0; i < size; i++) { int cur = queue.poll(); for (int coin : coins) { int next = cur + coin; if (next == amount) return steps + 1; if (next > amount) continue; if (!visited[next]) { visited[next] = true; queue.offer(next); } } } steps++; } return -1; } }✅ 思路极其清晰
❌ 实际性能一般（队列 + 访问数组）
🚀 解法二：DP（面试必写）
状态定义
dp[i] = 凑出金额 i 所需的最少硬币数状态转移
dp[i] = min(dp[i - coin] + 1)代码（面试首选 ✅）
class Solution { public int coinChange(int[] coins, int amount) { int[] dp = new int[amount + 1]; Arrays.fill(dp, amount + 1); dp[0] = 0; for (int i = 1; i <= amount; i++) { for (int coin : coins) { if (i >= coin) { dp[i] = Math.min(dp[i], dp[i - coin] + 1); } } } return dp[amount] > amount ? -1 : dp[amount]; } }复杂度
指标 | 结果 |
|---|---|
时间复杂度 | O(amount × len(coins)) |
空间复杂度 | O(amount) |
✅ 稳
✅ 好写
✅ 面试官最爱
🚀 解法三：贪心？不行（重要认知）
很多人会问：
能不能用贪心？每次选最大面值？
结论：不行 ❌
反例：
coins = [1, 3, 4, 5] amount = 7贪心：5 + 1 + 1 = 3 枚
最优：3 + 4 = 2 枚
👉零钱兑换 ≠ 贪心
🎯 我学到的东西
这题让我彻底想通了一件事：
问题 | 本质 |
|---|---|
完全平方数 | 数学定理 |
零钱兑换 | 无环最短路径 |
跳跃游戏 II | 必须跳的决策 |
你不是在枚举答案，而是在剪掉不可能的路。
⚠️ 易错点总结
误区 | 正确做法 |
|---|---|
用贪心 | 老老实实 DP |
dp 初值设为 0 | 应设为 INF |
忘记判断无解 | 最后检查 dp[amount] |
BFS 忘记 visited | 会超时 |
🧩 一句话总结
零钱兑换 = 完全背包 + 最少数量 + 最短路径
🎤 面试收尾（建议直接背）
“这道题我可以用三种思路来看：
第一种是 BFS，把它当成最短路径问题；
第二种是动态规划，时间复杂度 O(amount × coins)；
第三种是证明贪心不可行，说明为什么必须用 DP。
实际面试中，我会先写 DP 保底，再讨论 BFS 和优化空间。”