零钱兑换

零钱兑换求凑出目标金额的最少硬币数。每次先拿最大可用面额是贪心策略，对某些币制有效，对任意面额却不保证最优。动态规划先解决较小金额，再复用答案，时间为 O(amount × coins)。本课假设面额为正整数、每种可用无限枚。

自定义面额应使用 DP，或先证明贪心选择成立。画布把两种策略放在同一数轴，每次跳跃跨过一枚硬币的面额，展示局部选择与完整子问题比较的差异。

零钱兑换如何工作

贪心从 remaining = amount 开始，反复选择不超过剩余金额的最大面额，扣除并计数。剩余为 0 表示凑成，但未必最少；还有余额却无币可用，表示该贪心路径失败，不能单凭它断言无解。

DP 状态 dp[a] 是凑出金额 a 的最少枚数。dp[0] = 0，其余初始化为无穷，表示尚不可达。

逐金额从小到大，遍历每种面额 c。若 c ≤ a 且 dp[a - c] 有限，候选为：

dp[a - c] + 1

先用最少枚数凑出 a-c，再加一枚 c。比较全部面额后取最小；没有有限候选则保持无穷。正面额保证依赖金额更小，已经计算完成。

最终 dp[amount] 有限就返回它，否则返回 -1。需要硬币列表时，在各格记录获胜面额，从最终金额反向减去它，直到 0。

逐步演示

默认面额 1, 3, 4，目标 6。

先看贪心：先取 4，剩 2；3、4 都放不下，再取 1、1，剩 0。组合 4 + 1 + 1，三枚，虽然凑齐却不是最少。

再看 DP：dp[0] = 0，其余无穷。

• dp[1]：只有 1 可用，dp[0] + 1 = 1。
• dp[2]：只有 1 可用，dp[1] + 1 = 2。
• dp[3]：面额 3 得 dp[0] + 1 = 1，面额 1 得 dp[2] + 1 = 3，取 1 枚。
• dp[4]：面额 4 得 1 枚，面额 3、1 都得 2 枚，取 4。
• dp[5]：面额 4 读 dp[1] + 1 = 2，面额 3 得 3，面额 1 读 dp[4] + 1 = 2。最小为 2，按本课顺序保留面额 4。
• dp[6]：面额 4 读 dp[2] + 1 = 3，面额 3 读 dp[3] + 1 = 2，面额 1 读 dp[5] + 1 = 3。选择 3，得 2 枚。

全表 dp = [0, 1, 2, 1, 1, 2, 2]。

回溯：金额 6 的获胜币为 3，记录后到金额 3；该格也选 3，再到 0。组合 3 + 3，两枚，比贪心少一枚。

计算 dp[6] 前，dp[3] 已是最优，不需要反复撤销以前的决定。最终回溯只是恢复方案。切换 Canonical 的 1, 2, 5 看两者一致；Impossible 的 3, 5、目标 7，DP 返回 -1。

时间与空间复杂度

这里 coins 指面额种数，贪心成本包括排序与逐枚输出。DP 依赖金额数值，是伪多项式算法；金额很大时不能只因循环规则简单就视为便宜。

边界情况

• 金额 0：dp[0] = 0，不取币，是所有可达路径的基础。
• 面额大于当前金额：不是当前格的候选。
• 无解：3, 5 凑 7 时 dp[7] 保持无穷，返回 -1；贪心先取 5，余 2 后卡住。
• 贪心正确的币制：1, 2, 5 凑 11 时，两者都用三枚。贪心不是总错，而是需要成立条件。
• 返回 -1：DP 已检查全部合法末币，说明无组合可达，不是尚未算完。

常见错误

• 无条件信任最大面额优先。 默认 greedy-fails 的 1、3、4 就是反例。
• 把不可达状态初始化为 0。 会让无解金额看起来免费可达，破坏最小值。
• 从无穷状态构造有效候选。 dp[a - c] 必须有限；无穷加一仍不是解。
• 混淆最少枚数与方案数。 本课做 min；计数组合需要另一套状态转移。
• 向前恢复硬币。 应从最终金额沿获胜面额向后减。

简化范围

本课用少量面额，在数轴上对照贪心与 DP。日常币制常让贪心表现良好，这不构成任意面额的证明。算法已经使用按金额的一维表；实际程序可按是否需要方案决定是否保存前驱，也无需动画数轴。本课用于解释递推，不是包含所有输入约束和工程策略的完整兑换系统。