硬币找零这个问题几乎每个刚接触贪心算法的人都会碰到。题目本身不复杂手里有1元、5元、10元、50元、100元、500元六种面额的硬币各若干枚要用它们凑出A元问最少用多少枚。很多人第一反应是从大往小拿这个直觉对不对、什么时候对、什么时候会翻车才是这道题真正值得聊的地方。我见过太多人背下贪心找零的模板代码就去刷题结果遇到面额组合不规整的用例直接懵掉。这篇就把这道题从直觉到证明、从代码到边界条件完整拆一遍适合刚学贪心的人打地基也适合已经写过但没深究过正确性的人补课。1. 为什么从大往小拿这个直觉值得先信一次1.1 生活里的找零经验从哪来你去便利店买瓶水收银员找你零钱几乎不会给你一把一毛硬币而是先看有没有整块、再看五块十块。这个行为背后其实就是在做贪心每一步都优先用面额最大的、且不超过当前剩余金额的硬币。我们从小观察到的找零方式本质上就是这套策略的日常版本所以从大往小的直觉不是凭空来的它是被真实货币体系反复训练出来的。关键在于人民币这套面额设计本身是有讲究的。1、5、10、50、100、500 这几个数任意相邻两个面额之间大的那个都是小的那个的整数倍或者接近整数倍的关系。1 到 5 是 5 倍5 到 10 是 2 倍10 到 50 是 5 倍50 到 100 是 2 倍100 到 500 是 5 倍。这种倍数链结构正是贪心能够成立的结构性前提。你可以把它想成一套进制不规整但层级清晰的货币体系每一层都能被上一层整除或近似整除所以大面额永远装得下小面额的需求。1.2 贪心策略的精确表述把直觉翻译成可执行的规则其实就三步。第一步从面额最大的硬币开始考虑第二步在不超过剩余待凑金额的前提下尽可能多地使用当前面额第三步扣掉已用金额换下一个更小的面额重复直到凑齐。用伪代码描述就是对每个面额从大到小取min(该面额硬币数量, 剩余金额 / 该面额)枚然后更新剩余金额。这里有个细节很多人写代码时会忽略取的数量要同时受两个约束一是你手里这种硬币的实际枚数二是剩余金额还能容纳多少枚。少了任何一个约束都会出错。比如你手里只有 2 枚 500但剩余金额是 2000你不能取 4 枚只能取 2 枚剩下的靠更小面额补。反过来剩余金额只有 300哪怕你有 100 枚 500也一枚都用不上。这个双约束取小是整段逻辑的核心写的时候务必把min的两个参数都想清楚。1.3 一个必须先确认的前提在动手之前有一件事必须先确认所有硬币的总面值是否够凑出 A 元。如果不够那这题根本无解直接返回失败即可不需要进入贪心流程。这个检查看起来废话但实际工程里经常有人漏掉导致程序在凑不齐的情况下还在傻傻地循环最后返回一个错误的枚数。我的习惯是在最开头就把总金额算出来和 A 比一下不够就直接短路返回。这一步成本极低却能挡掉一大类边界 bug。2. 贪心在这道题上为什么真的成立2.1 用交换论证把直觉变成证明光说因为面额是倍数关系所以贪心对是不够的得能说清楚为什么。这里用经典的交换论证思路假设存在一个最优解它没有优先使用最大面额那么我们可以把这个最优解改造成贪心的形式且枚数不会变多。具体来说如果最优解里用了若干小面额硬币来凑一个本可以用更大面额覆盖的金额由于大面额是小面额的整数倍我们总能把若干小硬币替换成等值的大硬币枚数只会减少或持平。反复做这种替换最终就能得到贪心解且不劣于原最优解。既然贪心解不劣于最优解而它本身又是一个可行解那它必然就是最优解之一。这个论证能成立完全依赖大面额能被小面额整除这个性质。一旦这个性质被破坏交换论证就断了贪心也就不再保证最优。这一点在后面讲反例时会反复用到先在这里埋个伏笔。2.2 倍数链结构是贪心的命门把六种面额排成一条链1 → 5 → 10 → 50 → 100 → 500。每往上一级面额都是下一级的整数倍5倍或2倍交替。这种结构保证了任何一个较大面额都可以被若干个相邻的较小面额精确表示且表示所需的枚数在贪心意义下是最少的。举个具体的10 元可以由 2 枚 5 元表示也可以由 10 枚 1 元表示贪心会选 2 枚 5 元这确实是最少的。50 元可以由 5 枚 10 元表示贪心选 5 枚 10 元也是最少。每一级都成立整条链就成立。反过来想如果面额是 1、3、4 这种4 不能被 3 整除链就断了。凑 6 元时贪心会先拿 4剩 2 用两个 1共 3 枚但最优是 33只要 2 枚。这就是倍数链断裂导致的贪心失效。所以判断一道找零题能不能用贪心第一件事就是检查面额序列是否满足每个面额都是前一个面额的整数倍严格说是每个面额能被所有更小面额整除或者至少相邻满足倍数关系且整体构成规范体系。2.3 硬币数量受限时结论还稳吗有人会担心题目里每种硬币数量是有限的不是无限供应这会不会破坏贪心的最优性答案是在倍数链结构下数量受限并不影响贪心的正确性。原因在于贪心在每一步取的是当前能取的最大枚数如果这个枚数被手里的实际数量卡住了说明这种面额已经用尽后续只能用更小面额补而更小面额本来就能精确表示剩余金额因为倍数关系所以不会出现因为大面额不够用而导致整体枚数变多的情况。换句话说数量限制只会让贪心提前换小面额但换过去之后依然是最优的。不过这里有个隐含条件剩余金额必须能被更小面额精确凑出。在本题的面额体系下这是天然成立的因为最小面额是 1 元任何整数金额都能用 1 元补齐前提是 1 元硬币够。如果最小面额不是 1比如只有 5、10、50那凑 3 元就无解了这时候数量限制和无解判断就要一起考虑。本题有 1 元兜底所以只要总金额够就一定凑得出。3. 把算法写成能跑的代码3.1 核心循环的写法与陷阱先看一段 Python 实现把六种面额和对应数量组织成两个平行数组从大到小遍历def min_coins(amount, counts): # counts 顺序对应 [1, 5, 10, 50, 100, 500] denominations [500, 100, 50, 10, 5, 1] count_map {1: counts[0], 5: counts[1], 10: counts[2], 50: counts[3], 100: counts[4], 500: counts[5]} total sum(d * count_map[d] for d in denominations) if total amount: return -1 # 凑不齐 used 0 remaining amount for d in denominations: take min(count_map[d], remaining // d) used take remaining - take * d if remaining 0: break return used if remaining 0 else -1这段代码里最容易写错的地方是remaining // d的整除。Python 的//对正数是向下取整正好符合最多能放几枚的语义。但如果金额或面额出现负数本题不会整除行为会变得反直觉所以实际工程里我会加一句断言确保输入非负。另一个坑是count_map的构建如果直接按数组下标对应很容易把 1 元和 500 元的顺序搞反导致从最大开始遍历时实际拿到的是最小面额。我的做法是显式用字典把面额和数量绑定虽然多写几行但可读性和正确性都更有保障。3.2 用 C 再写一遍看边界换 C 写主要是为了看清整数运算和数组边界#include vector #include algorithm using namespace std; int minCoins(int amount, vectorint counts) { int denom[6] {500, 100, 50, 10, 5, 1}; int cnt[6] {counts[5], counts[4], counts[3], counts[2], counts[1], counts[0]}; long long total 0; for (int i 0; i 6; i) total 1LL * denom[i] * cnt[i]; if (total amount) return -1; int used 0, remaining amount; for (int i 0; i 6 remaining 0; i) { int take min(cnt[i], remaining / denom[i]); used take; remaining - take * denom[i]; } return remaining 0 ? used : -1; }C 版本里我特意把total声明成long long因为面额最大 500、数量如果给到很大比如每種 10 万枚总金额会超过 32 位 int 的范围。虽然本题的 A 元通常不会那么大但养成用 64 位累加的习惯没坏处尤其是这类数量 × 面额的求和场景溢出是静默发生的不报错但结果错排查起来很痛苦。另外remaining / denom[i]在 remaining 为正时是安全的循环条件里加了remaining 0提前退出避免无谓遍历。3.3 复杂度与实测表现时间复杂度是 O(6)也就是常数级因为面额种类固定为 6 种跟 A 的大小无关。空间复杂度 O(1)。这意味着哪怕 A 给到十亿级别程序也是瞬间出结果。我实测过把 A 设成 10^9、每种硬币给 10^6 枚Python 版本跑下来也在毫秒级瓶颈根本不在算法本身而在输入解析。这也提醒一点这类题如果出现在笔试里考察的绝不是性能而是你对贪心正确性的理解和边界处理是否周全。别在优化上浪费时间把边界想全才是得分点。4. 那些让贪心翻车的反例长什么样4.1 构造一个面额不规整的体系前面反复强调倍数链现在动手造一个反例感受一下。假设面额是 1、3、4要凑 6 元。贪心从 4 开始拿 1 枚 4剩 2只能用两个 1总共 3 枚。但最优解是两枚 3只要 2 枚。贪心在这里多用了 1 枚。这个反例的精髓在于 4 和 3 之间没有整除关系导致先用大的反而堵死了后面更优的组合。再换一组面额 1、5、6、9凑 11 元。贪心先拿 9剩 2用两个 1共 3 枚最优是 562 枚。又是贪心翻车。你会发现这类反例有个共同特征存在某个金额用一个大面额加若干小面额凑不如用两个中等面额凑更省。只要面额体系里存在这种中等面额组合优于大面额的情况贪心就不保证最优。4.2 本题为什么不会出现这种反例回到本题的 1、5、10、50、100、500。要构造类似的反例需要找到某个金额使得一个大面额 小面额的枚数多于两个中等面额。但由于每个大面额都是中等面额的整数倍比如 10 2×550 5×10任何用大面额表示的金额都能被等值的中等面额组合替代且枚数关系是确定的1 枚 10 元 2 枚 5 元枚数变多反过来 2 枚 5 元想替代 1 枚 10 元枚数变少。贪心永远优先选枚数更少的那个方向所以不可能出现贪心选了枚数多的组合的情况。这就是倍数链的威力它让面额大和枚数少这两个目标始终同向不会打架。4.3 一张表看清贪心适用边界面额体系是否满足倍数链贪心是否最优典型反例1,5,10,50,100,500是是无1,2,5,10,20,50,100是近似是无1,3,4否否凑6贪心3枚 vs 最优2枚1,5,6,9否否凑11贪心3枚 vs 最优2枚1,7,10否否凑14贪心5枚(101×4) vs 最优2枚(77)这张表建议存下来遇到任何找零题先对照一下面额体系。满足倍数链的放心用贪心不满足的老老实实上动态规划。动态规划的思路是dp[i] min(dp[i - 面额] 1)对所有面额取最小复杂度 O(A × 面额种类数)虽然比贪心慢但保证正确。本题因为满足倍数链用贪心是既快又对属于可以偷懒的情况。5. 输入输出与边界处理的实战细节5.1 输入格式的几种常见变体这类题在真实场景里的输入格式五花八门。有的是先给六个整数表示各面额数量再给 A有的是先给 A 再给数量还有的把面额和数量成对给出。写通用代码时我习惯先把输入读成一个列表再按约定切分而不是硬编码input().split()的下标。比如data list(map(int, input().split())) counts data[:6] # C1, C5, C10, C50, C100, C500 amount data[6]这样即使题目把 A 放在前面也只需要改一行切片。硬编码下标是这类题最常见的低级错误来源尤其是六个数量加一个金额共七个数字数错一个位置就全盘皆输。我的经验是凡是超过三个字段的输入一律先整体读入再按语义切分别在split的返回值上直接索引。5.2 零金额和超大金额怎么处理A 0 的情况最少硬币数就是 0不需要任何硬币。很多代码在remaining 0时直接进循环虽然循环体里remaining // d都是 0最终也返回 0逻辑上没错但多跑了一轮。更稳妥的写法是在开头判断if amount 0: return 0语义清晰。超大金额方面前面提过用 64 位累加总面值另外要注意remaining // d的结果可能很大如果语言里整数有上限比如某些嵌入式环境的 32 位要提前评估。本题场景下 A 通常不会超过总面值所以实际风险不大但习惯要养好。5.3 凑不齐时的返回值约定凑不齐有两种情况总面值不够或者总面值够但某种面额缺失导致无法精确凑出。本题因为有 1 元兜底只要总面值够就一定能凑出所以第二种情况不会发生。但写通用函数时我习惯统一返回 -1 表示失败并在文档里写清楚。有些题目要求返回 0 或者抛异常具体看约定。这里的关键是函数内部要有一个明确的失败出口而不是让remaining带着非零值悄悄返回一个错误的枚数。我在代码里用return used if remaining 0 else -1这一句兜底就是为了防止这种静默错误。6. 从这道题能带走的通用思路6.1 判断贪心能否用的三步检查拿到任何一道求最少/最多的题想用贪心之前我会走三步检查。第一步看问题有没有最优子结构也就是大问题的最优解能不能由小问题的最优解拼出来第二步看有没有贪心选择性质也就是每一步的局部最优能不能导向全局最优这一步往往要靠交换论证来验证第三步看数据本身有没有结构性保证比如本题的倍数链。三步都过才敢放心用贪心。任何一步存疑就退回动态规划或者搜索别赌。这道题之所以是贪心的经典入门题正是因为它三步全过而且结构清晰到可以用肉眼验证。但恰恰因为太经典很多人只记住了从大往小拿这个结论没记住背后的三步检查换个面额体系就翻车。我见过有同学在面额是 1、3、4 的题上照样写贪心跑出来答案错了还以为是代码 bug其实是策略选错了。这种错误比语法错误更隐蔽也更值得警惕。6.2 贪心和动态规划的分界线在哪简单说贪心是一条路走到黑每步都选当前最好动态规划是把所有可能都算一遍取全局最好。贪心快但挑场景动态规划慢但通吃。找零问题里面额满足倍数链就用贪心不满足就用动态规划这条分界线非常清晰。更一般地凡是局部最优能推出全局最优的场景贪心都值得一试凡是局部最优可能堵死全局最优的场景就得老老实实枚举状态。我在实际项目里遇到资源分配、任务调度这类问题时也是先问一句局部最优会不会打架。如果各个决策之间相互独立、互不影响贪心往往成立如果前一个决策会改变后一个决策的可行域那就要小心多半得上动态规划或者更复杂的算法。这道硬币题的价值就在于它用最小的认知成本把这个判断过程完整演示了一遍。6.3 一个容易被忽略的验证习惯最后分享一个我自己的习惯写完贪心代码别急着提交先手动构造几个小用例跑一遍尤其是刚好凑整差一元某种硬币刚好用完这几类边界。比如 A 499手里 500 元硬币一堆贪心会跳过 500 直接用 100、50 等凑这时候要确认 499 确实能被凑出且枚数合理。再比如 A 刚好等于某种硬币面额确认贪心只取一枚而不是绕远路。这些手算验证花不了两分钟却能挡掉大部分逻辑漏洞。贪心代码通常很短短到让人放松警惕但短不等于简单边界往往就藏在那几行min和整除里。把这道题吃透你收获的不只是一段找零代码而是一套什么时候该信直觉、什么时候该怀疑直觉的判断框架。面额规整时大胆贪心面额刁钻时果断换算法这个分寸感比记住任何模板都值钱。
