企业官网建设流程全解析

硬币找零这个问题，几乎每个刚接触贪心算法的人都会碰到。题目本身不复杂：手里有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 枚；但最优是 3+3，只要 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, vector<int>& 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 枚；最优是 5+6，2 枚。又是贪心翻车。你会发现这类反例有个共同特征：存在某个金额，用一个大面额加若干小面额凑，不如用两个中等面额凑更省。只要面额体系里存在这种"中等面额组合优于大面额"的情况，贪心就不保证最优。

4.2 本题为什么不会出现这种反例

回到本题的 1、5、10、50、100、500。要构造类似的反例，需要找到某个金额，使得"一个大面额 + 小面额"的枚数多于"两个中等面额"。但由于每个大面额都是中等面额的整数倍，比如 10 = 2×5，50 = 5×10，任何用大面额表示的金额，都能被等值的中等面额组合替代，且枚数关系是确定的：1 枚 10 元 = 2 枚 5 元，枚数变多；反过来 2 枚 5 元想替代 1 枚 10 元，枚数变少。贪心永远优先选枚数更少的那个方向，所以不可能出现"贪心选了枚数多的组合"的情况。这就是倍数链的威力：它让"面额大"和"枚数少"这两个目标始终同向，不会打架。

4.3 一张表看清贪心适用边界

这张表建议存下来，遇到任何找零题先对照一下面额体系。满足倍数链的，放心用贪心；不满足的，老老实实上动态规划。动态规划的思路是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和整除里。

把这道题吃透，你收获的不只是一段找零代码，而是一套"什么时候该信直觉、什么时候该怀疑直觉"的判断框架。面额规整时大胆贪心，面额刁钻时果断换算法，这个分寸感，比记住任何模板都值钱。