零钱兑换

贪心收银员的陷阱：拿最大面额 ≠ 用最少硬币

人人都会背 dp[a]=min(dp[a-c]+1)，却很少有人能讲清贪心为什么会错。这里把它做成可玩的：你来决定每个金额「最后一枚硬币剥哪个」，即时看到命中、连击与星级；再用反例沙盒亲手让贪心翻车。

完全背包 · 最值时间 O(amount·coins)空间 O(amount)

先别背公式 · 贪心为什么会翻车

贪心：拿最大面额

4 + 1 + 1

3 枚

最优：DP 枚举

3 + 3

2 枚

coins=[1, 3, 4] 凑 6：最大的一步会把余额推到一个「难凑」的数。要稳拿最优，必须站在每个金额上，枚举「最后一枚硬币是哪个」，取最小 —— 这就是 DP。

命中 0%0/0 连击 0 最佳 0

填 dp[1] / dp[6]

←

绿已定稿 · 蓝当前 a · 紫候选会跳回的子问题 · 红 ∞ 暂不可达 · · 尚未计算

凑出 1 元，最后一枚硬币剥哪个最省？

设计哲学 · 为什么真实生活里贪心找零没问题？

真实货币 [1, 5, 10, 25] 是「标准币制(canonical)」—— 数学上能证明贪心拿最大面额永远等于最优，所以收银员从不出错。但面试给的是任意面额，比如 [1,3,4]，它不是标准币制，贪心立刻翻车。这就是为什么这题默认必须上 DP：你不能赌币制刚好是标准的。

LC279 完全平方数 —— 面额=平方数的同款完全背包最值LC518 零钱兑换 II —— 求组合数（遍历顺序不同）LC377 组合总和 Ⅳ —— 求排列数

贪心拿最大面额不一定最优 —— coins=[1,3,4] 凑 6：贪心 4+1+1=3 枚，最优 3+3=2 枚。最大的一步会把余额推到难凑的数。
不可达要用哨兵，别直接返回 dp[amount] —— 凑不出时 dp[amount] 还是 ∞（代码里是 amount+1 上界）。最后要判 dp[amount] > amount 才返回 -1。
完全背包：金额正序遍历 —— 每种硬币可重复使用，金额从小到大正序刷新；别和 0/1 背包的倒序搞混。
求最少枚数，不是方案数 —— 这题是最值 min；求「有几种凑法」是 LC518，遍历顺序和转移都不同。