从能算到秒杀：零钱兑换与「最少硬币」的数学真相

如果说279. 完全平方数​ 是在考你最少用几个平方数拼出一个数那322. 零钱兑换​ 就是它的「现实版」最少用几枚硬币凑出一个金额这也是我第一次真正明白一句话所有「最少数量」的问题本质都是最短路径。 题目速览LeetCode 322. 零钱兑换中等给你一个整数数组coins表示不同面额的硬币再给你一个整数amount表示总金额。请你计算凑出 amount 所需的最少硬币个数。每种硬币无限使用如果无法凑出返回-1示例输入coins [1,2,5], amount 11 输出3 解释11 5 5 1输入coins [2], amount 3 输出-1 我的第一反应很真实看到「最少数量」大脑自动弹出三个词BFSDP背包问题于是立刻写出dp[i] min(dp[i - coin] 1)✅ 对❌ 但不够因为这题真正的坑在于amount 很大coins 很小不能只靠直觉 解法一BFS最直观把问题看成一张图节点金额0 ~ amount边减去一枚硬币目标从0 → amount的最少步数class Solution { public int coinChange(int[] coins, int amount) { QueueInteger 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必须跳的决策你不是在枚举答案而是在剪掉不可能的路。⚠️ 易错点总结误区正确做法用贪心老老实实 DPdp 初值设为 0应设为 INF忘记判断无解最后检查 dp[amount]BFS 忘记 visited会超时 一句话总结零钱兑换 完全背包 最少数量 最短路径 面试收尾建议直接背“这道题我可以用三种思路来看第一种是 BFS把它当成最短路径问题第二种是动态规划时间复杂度 O(amount × coins)第三种是证明贪心不可行说明为什么必须用 DP。实际面试中我会先写 DP 保底再讨论 BFS 和优化空间。”