贪心 vs. DP：硬币找零问题的30秒测试
Source: Dev.to
最初发布于 LeetCopilot Blog
TL;DR
- Topic: 决定在硬币找零变体中使用贪心还是动态规划。
- Why it matters: 选择错误的策略会浪费时间并让面试官困惑。
- Core steps: 检查硬币系统属性，测试反例，当最优子结构不明确时回退到 DP。
- Key insight: 标准（canonical）硬币系统是例外，而非常态。
- You’ll learn: 一个快速启发式方法，TypeScript DP 代码片段，以及练习题。
初学者友好解释
贪心何时有效
贪心是安全的当硬币系统是 canonical——每个更大的硬币都是较小硬币的倍数或结构化组合。
示例: USD 硬币 (1, 5, 10, 25) 在找零时是规范的，能够使用最少硬币。
贪心何时失效
如果较大的硬币不是由较小的硬币组合而成，贪心可能会挑选一个局部看起来好的硬币，却破坏全局最优。
示例: 硬币 [1, 3, 4]，目标 6。贪心会选 4 + 1 + 1（3 枚）而不是 3 + 3（2 枚）。
为什么 DP 能拯救你
DP 会遍历所有子目标。自底向上的表格化保证了最少硬币数，只要你定义类似的递推式
dp[x] = min(dp[x - c]) + 1 for every coin c直观概念
想象两列：贪心路径（选择最大，减去，重复） versus DP 表（从 0 填到目标）。DP 列永远不会忘记更好的子解。
步骤式学习指南
1) 运行反例测试
在编码之前，先在脑中测试一个小的反例：尝试用硬币 [1,3,4] 构成 6。如果贪心算法失败，你必须使用 DP。这种快速检查有助于你清晰地解释推理过程，类似于 greedy algorithm counterexamples for coding interviews 中的做法。
2) 确定状态与转移
对于最少硬币问题，状态是目标金额。转移时检查每一种硬币：
dp[x] = Math.min(dp[x], dp[x - coin] + 1) // 当 x - coin >= 0 时3) 处理不可达状态
将所有条目初始化为 Infinity，仅 dp[0] = 0。如果 dp[target] 仍为 Infinity，返回 -1。
4) 说明复杂度
提到自底向上的做法时间复杂度为 O(n × amount)，空间复杂度为 O(amount)。面试官喜欢听到你了解这些权衡。
5) 用两个目标练习
分别用硬币集合 [1,3,4] 求解 6，和用硬币集合 [1,5,10,25] 求解 27。比较贪心和 DP 的答案，以巩固这一本能。
可视化示例：自底向上硬币找零（TypeScript）
function minCoins(coins: number[], amount: number): number {
const dp = Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let total = 1; total = 0) {
dp[total] = Math.min(dp[total], dp[total - coin] + 1);
}
}
}
return dp[amount] === Infinity ? -1 : dp[amount];
}每个 total 都复用了最佳的子目标解，这些是贪心算法可能会错过的。
实用准备策略
构建自己的决策表
创建一个两列的表格：贪心算法有效的硬币集合，以及贪心失效的硬币集合。为每个集合添加简短备注。结合如何判断何时需要动态规划一起复习，以加强模式识别。
在计时下进行练习
给自己五分钟时间，对三个随机硬币系统进行分类并求解。压力有助于让启发式方法牢记。
使用轻度指导
像 LeetCopilot 这样的助手可以提示你在开始编码前先给出反例，从而在不泄露动态规划解法的前提下强化严谨的推理。
关联其他模式
注意这与滑动窗口决策的相似之处：仅在单调性属性成立时才使用贪心。该滑动窗口可视化工具可以训练你观察不变量的直觉。
常见错误需避免
假设美元规则适用于所有情况
外币或自定义硬币系统常常会破坏贪心假设。
忘记初始化
默认将 dp 设为零会错误地偏向不可能的状态。
忽略负数或零硬币
验证输入；硬币应为正数，否则循环可能无限执行。
未对不可达目标返回 -1
面试官期望在不存在组合时给出明确的信号。
FAQ
How do I know greedy is valid?
尝试一个小的反例。如果贪心算法使用的硬币比其他方案更多，就改用 DP。
What should I practice before coin change?
基本的循环、数组初始化，以及子问题的思考。然后学习如何解释递推式。
Is this topic important for interviews?
是的。它考察模式选择能力，而不仅仅是编码能力。
Can I optimize the DP further?
可以——如示例所示使用一维数组，并且剪枝掉大于目标值的硬币以减少工作量。
结论
在硬币找零问题中，在贪心算法和 DP 之间的选择取决于对硬币系统结构的证明或反驳。先给出反例，如果不确定则回退到 DP，并阐述你的推理。通过练习，这一决定会变得自动且在面试中安全。
如果你在寻找一个 AI 助手帮助你掌握 LeetCode 模式并准备编码面试，请查看 LeetCopilot。