最少纸币张数入门：人民币支付贪心与整除取模题解

刷入门算法题单的时候，编号3033这道"人民币支付"几乎是绕不开的一站。它顶着"例8.1"的编号出现，说明出题人把它当作整除与取模思想的第一道样板题。题面很朴素：手里有若干张100元、50元、20元、10元、5元和1元面额的人民币，给定一个金额，问最少要用多少张纸币才能凑出这个数。看起来是生活里每天都在发生的事，但把它翻译成代码，牵扯到的却是贪心策略成立与否、除法与取模如何配对、边界值怎么处理这一整套基本功。这道题适合刚学完输入输出和四则运算的同学打地基，也适合已经写过不少代码的人回头确认一下自己对贪心的直觉是否可靠。我下面就把这道题从题意拆解、原理证明、代码落地到常见翻车点，完整地捋一遍。

1. 题目到底在问什么，解法为什么这么选

1.1 把生活场景翻译成数学语言

"人民币支付"这个标题听起来像一道业务题，实际上它的内核是一个整数拆分问题。给定一个正整数金额 n，再给定一个面额集合 {100, 50, 20, 10, 5, 1}，要求用这个集合里的数相加凑出 n，并且使用的数字个数尽可能少。这里有个隐含前提，就是每种面额的数量在题目里默认是"无限张"——现实中你钱包里可能只有两张50元，但题目不限制每种面额的张数，想用多少用多少，只要凑出来就行。

把生活场景抽象到这一步之后，问题的形状就清楚了：它是一个"用最少的硬币凑出指定金额"的经典模型，只不过硬币的面额换成了人民币。很多同学一看到"最少"两个字就条件反射想到动态规划，这没错，但对于这组特定面额，其实有更省事的做法。关键在于面额集合本身的气质——它不是一个随意的数字堆，而是一套经过精心设计、彼此之间有整除关系的面额体系。抓住这一点，整道题的解法就豁然开朗了。

这里顺便说一句，题面在有些版本里要求输出"一共需要多少张纸币"，在另一些版本里则要求"分别输出每种面额的张数，从100元到1元各占一行"。这两种版本的代码差别不大，但输出格式完全不同，读题时务必确认清楚，不然逻辑对了照样过不了评测。我后面两种都会给出来，你对着自己的题面对号入座即可。

1.2 贪心策略在这里为什么是成立的

面对"最少张数"这个目标，最自然的想法就是贪心：能拿大面额就拿大面额，先尽可能用100元，剩下的用50元，再剩下用20元，一路往下直到1元补齐。这个思路的直觉来源是"大面额顶好几张小面额"，用大面额显然更省张数。但贪心算法有个致命弱点——局部最优不等于全局最优，很多题目里"眼前拿最大的"最后会掉进坑里。

那为什么这道题可以放心贪心呢？答案藏在人民币面额的设计规律里。你仔细看这组数：100和50是两倍关系，50和20、20和10、10和5、5和1，相邻面额之间要么是整数倍，要么有足够的"中间面额"兜底。更具体地说，任何一个面额，都不会出现"用一张大面额反而凑不出最优解"的情况。举个可能出错的情形来体会：假设金额是18元，如果贪心先拿10元，剩8元，再拿5元，剩3元，最后3张1元，共5张；就算你不拿10元，改用9张1元，那是9张，明显更差。贪心没有吃亏。

真正的反例出现在面额设计"不规整"的时候。比如面额集合是 {1, 3, 4}，要凑6元，贪心会先拿4元，剩2元，只能拿2张1元，总共3张；但最优解是3元加3元，只要2张。这里贪心就翻车了，原因是4和3之间没有整除关系，也没法用一个大面额去覆盖小面额的最优组合。人民币这套面额恰恰避开了这种结构，所以"能用大的就用大的"在这道题里是安全的。严格一点说，对于这类"每个较大面额都是较小面额某种整数组合的倍数或能被其整除"的规范面额体系，贪心法能保证得到全局最优解。这也是为什么教材把它放在贪心思想的入门位置——它是一道能让初学者放心体验贪心的样板题，不会一上来就用反例把你劝退。

1.3 三种实现路线的取舍对比

知道思路之后，落地方式有好几种，我在不同阶段都用过，各有适用场景。

第一种是硬编码写法，把六个面额依次写死六段"除法加取模"，代码直白，看一眼就懂，适合刚学语法的同学。缺点是扩展性差，面额一变就要重写，而且六段重复代码看着有点笨。

第二种是数组加循环写法，把面额存进一个数组，从大到小遍历，每轮做一次整除和取模。代码短、干净、好维护，面额改了只要改数组，是我最推荐的写法。

第三种是动态规划，用 dp 数组记录凑出每个金额所需的最少张数，从1一直推到大金额。这个写法对于本题属于"杀鸡用牛刀"，代码更长、运行更慢，但它有一个硬核优势——面额不规整时它照样正确。所以它更适合作为"万一贪心失效怎么办"的后手，我放在后面的拓展部分讲。

把这三条路线摆在一起看，本题的最优选择很明确：用数组循环的贪心写法，既简洁又正确。但你要明白为什么能这么选，而不是背下代码交差，否则换一道面额就懵了。

2. 核心细节解析：整除、取模和那些容易忽略的边界

2.1 除法与取模为什么必须配对使用

这道题最核心的两行操作就是整除和取模。以100元为例，表达式n / 100得到的是"最多能塞进去几张100元"，而n % 100得到的是"塞完100元之后还剩多少钱"。这两个操作必须成对出现，缺一不可。

很多初学者容易犯的错误是只做除法不做取模，比如算出100元的张数后，还拿着原始金额去算50元，结果50元的张数就重复计算了已经用100元覆盖掉的部分。正确的流程是：每确定完一种面额的张数，就立刻把金额更新为余数，让下一轮基于"剩下的钱"继续算。这样一路滚下去，金额会单调递减，直到最后剩下不到5元的部分全部由1元补齐。

从数学角度看，这个过程的本质是把一个整数按面额从大到小做"进制分解"。每一步的商就是该面额的张数，余数交给下一位。它跟十进制数的数位拆解在思路上是同构的——拆一个数的百位、十位、个位，用的也是除以10取商、对10取余的套路。理解了这一层，你会发现"人民币支付"和"数字拆分"是同一类思维，只不过这里每位"允许的取值范围"由面额体系决定。

2.2 输入输出格式里最容易踩的坑

读题这件事，说起来简单，栽进去的人却特别多，我列几个这道题里高频出现的格式陷阱。

第一个坑是"输出总张数"还是"分面额输出"。有的题面写着"输出最少需要多少张"，答案是单个整数；有的题面写着"输出各种面额的张数"，要求100元到1元每种占一行，共六行。这两种情况代码里的输出部分差别很大，逻辑对了格式错，一样判错。

第二个坑是"要不要输出0张"。在分面额输出的版本里，如果某个面额用不上，是输出0还是跳过不输出？绝大多数版本要求输出0占位，保持六行结构。但也有些变态版本要求只输出用到的面额，这就得加判断。稳妥做法是仔细看题面给的样例输出，样例长什么样你就跟着长什么样。

第三个坑是输入金额的取值范围。这类入门题通常限制金额不超过1000，也就是最多10张100元。知道这个上限之后，你可以反推出最大的答案张数不会超过1000张（全用1元的情况），用 int 存绰绰有余，不必担心溢出。但如果金额上限被改成很大的数，比如十亿级别，那 int 依然够用于计数，只是要注意除法结果可能超出预期，这时候就该考虑用 long long 保险一点。

2.3 面额数组的排序方向不能颠倒

用数组循环写法时，面额数组必须严格从大到小排列。这个细节看似无关紧要，其实直接决定算法对不对。因为贪心的前提是"优先用大面额"，如果你的数组是从1元开始遍历的，那就变成了优先用1元，最后算出来的张数会是最大的那个数，跟"最少"完全背道而驰。

我见过不少人写完数组循环，运行时发现答案是金额本身（比如输入638，输出638），愣半天不知道哪里错了，一查原来是面额数组顺序写反了。这个错误隐蔽性很强，因为程序不报错、逻辑也"跑通"了，只是结果是错的。所以每次写这类题，我都会在心里默念一遍"大的在前"。另外，如果题目要求你按100、50、20、10、5、1的顺序输出每种面额的张数，那读取和输出的顺序正好和贪心遍历的顺序一致，用一个数组就能同时兼顾计算和输出，非常顺手。

3. 完整实操：从零写出可提交的代码

3.1 C++ 版本逐行拆解

先看求总张数的版本，这也是最简短的写法。

#include <iostream> using namespace std; int main() { int n; cin >> n; int cnt = 0; // 记录总张数 cnt += n / 100; // 100元能拿几张 n %= 100; // 更新剩余金额 cnt += n / 50; // 50元能拿几张 n %= 50; cnt += n / 20; // 20元 n %= 20; cnt += n / 10; // 10元 n %= 10; cnt += n / 5; // 5元 n %= 5; cnt += n; // 剩下的不足5元，全部用1元，张数就是余额本身 cout << cnt << endl; return 0; }

最后一步cnt += n是个小巧思。当剩余金额小于5元时，只能全用1元，所以1元的张数恰好等于剩余金额本身，不需要再写n / 1和n %= 1，直接加上去就行。当然你也可以规规矩矩写cnt += n / 1，结果一样，只是啰嗦一点。

这段代码用了连续的除法和取模，没有循环，优点是直观，适合用它来验证自己是否彻底理解了流程。缺点是如果面额增加到十种，就要写十段，容易手抖写错。

再看分面额输出的版本，用数组循环会清爽很多。

#include <iostream> using namespace std; int main() { int n; cin >> n; int a[6] = {100, 50, 20, 10, 5, 1}; // 从大到小，顺序不能乱 for (int i = 0; i < 6; i++) { cout << n / a[i] << endl; // 当前面额的张数 n %= a[i]; // 更新余额 } return 0; }

这里每次循环先输出张数再更新余额，顺序很重要。如果先更新了余额再输出，那输出的就是下一次的面额张数，全错位了。这个坑我当年也踩过，输出结果整体上移一位，盯着看半天才发现是语句顺序反了。

3.2 Python 版本顺手验算

如果你平时用 Python 做题，同一套逻辑可以写得更紧凑。

n = int(input()) cnt = 0 for v in [100, 50, 20, 10, 5, 1]: cnt += n // v # 注意用整除 //，不是浮点除 / n %= v print(cnt)

Python 里有个特别容易掉进去的坑，就是除法运算符。如果你不小心写了n / v，得到的是浮点数，比如638 / 100结果是6.38，累加进计数器后输出会变成带小数的数，或者因为类型问题引发意想不到的结果。记住整除一定用//。我在初学阶段就因为这个小斜杠查了半天，明明逻辑没错，输出却是个小数，一度怀疑题目数据有问题。

Python 还有个便利之处，就是列表推导和内置函数能让"分面额输出"更短，但为了可读性，我建议还是老老实实写循环，逻辑清楚比炫技重要。

3.3 手算推演：拿一个样例从头走一遍

光看代码不够直观，我们拿输入 638 实际走一遍，确认每一步都对得上。

• 638 除以 100，商 6 余 38，说明100元拿6张，花掉600元，还剩38元；
• 38 除以 50，商 0 余 38，50元一张都不用，剩38元；
• 38 除以 20，商 1 余 18，20元拿1张，剩18元；
• 18 除以 10，商 1 余 8，10元拿1张，剩8元；
• 8 除以 5，商 1 余 3，5元拿1张，剩3元；
• 3 除以 1，商 3 余 0，1元拿3张。

总张数 = 6 + 0 + 1 + 1 + 1 + 3 = 12 张。回头验算金额：6×100 + 1×20 + 1×10 + 1×5 + 3×1 = 600 + 20 + 10 + 5 + 3 = 638，分毫不差。

你也可以自己换几个数试，比如输入 1，各面额商都是0，最后1元拿1张，输出1；输入 1000，100元拿10张，其余全0，输出10；输入 99，100元和50元都是0张，20元拿4张剩19，10元拿1张剩9，5元拿1张剩4，1元拿4张，总共4+1+1+4=10张。这几个边界值建议都手动跑一遍，比只看代码靠谱得多。

3.4 写成通用模板，方便日后复用

把这套逻辑抽象一下，就得到一个能处理任意"规范面额集合"的通用模板。

#include <iostream> #include <vector> using namespace std; int main() { int n; cin >> n; vector<int> a = {100, 50, 20, 10, 5, 1}; // 从大到小排列 int cnt = 0; for (int v : a) { cnt += n / v; n %= v; } cout << cnt << endl; return 0; }

这个模板的适用范围比你想象的要广。只要面额集合满足"从大到小、且贪心成立"这两个条件，无论是人民币、港币面额，还是虚构的某种货币，直接替换数组内容即可。比如某道题的面额是 {64, 16, 4, 1}，这是一套以4为倍率的规整面额，同样可以用这个模板秒过。以后遇到"最少硬币数"且面额规整的题，套上去就行，省去每次重推的时间。但请务必记住前提——贪心成立。一旦面额集合不规整，这个模板就会给出错误答案，那时候必须换动态规划。

4. 常见问题与排查技巧实录

4.1 高频错误速查表

我把这些年在这道题以及同类题上见过的错误整理成一张表，出问题时对着排查，能省下大量时间。

表格里第一条和第四条是新手最高频的错误，前者结果"看起来像那么回事但完全错"，后者往往会让张数爆炸式偏大。记住这两条，能挡掉一大半问题。

4.2 调试时怎么快速定位

遇到卡住的情况，我习惯用"打印中间量"这一招。在循环里每轮把当前面额、当前商、当前余数打出来，比如cout << v << " " << n / v << " " << n % v << endl;，运行一次就能看清金额是怎么一步步递减的。如果发现某一步余数没变小，那就说明取模那行漏了或者写错了；如果发现面额顺序是从小到大，一眼就能看出问题所在。

另一个实用技巧是拿最小样例测试。输入1、输入5、输入10 这几个值能快速验证边界处理是否正确。尤其是输入1，它会把所有面额商都为0的情况暴露出来，如果你的代码在这种极端输入下崩溃或输出异常，那大概率是数组访问越界或者初始值没处理好。

还有一点，做这类入门题别急着提交，先在本地把样例跑通，再用自己手算的几个值对比。人算和机算对上，基本上就没问题了。我养成的习惯是每道题至少手算两个样例，虽然费点时间，但比反复提交看红字反馈效率高得多。

4.3 几个只有实践才知道的小心得

第一个心得是关于变量更新的时机。无论用哪种写法，都要保证"确定张数"和"更新余额"是紧挨着的两步，中间不插入其他操作。我见过有人把六个面额的除法全写在前面，取模全写在后面，想当然地认为结果一样，其实金额根本没被正确递减，算出来完全错。原因就在于取模依赖前一步的余数，顺序被打乱就断了链条。

第二个心得是数组写法的索引问题。C++ 里数组下标从0开始，循环写成i < 6而不是i <= 6，多写一个等号就越界，程序可能崩溃也可能读到垃圾值，输出一个莫名其妙的数。这种错误在本地不一定报错，很坑，写的时候把数组长度和循环上限对一遍再提交。

第三个心得是关于可读性。入门题虽然简单，但代码写清楚了对后面做难题有好处。给变量起有意义的名字，比如用count而不是c，用remain而不是r，加上几行注释说明每步在干什么。等以后回头看，你会感谢当时写清楚的自己。这类题练的不只是算法，还有编码习惯，习惯好了，复杂题目的调试成本会低很多。

5. 举一反三：这道题还能往哪些方向扩展

5.1 面额不规整时贪心为什么会失效

前面反复强调贪心成立的前提是面额规整，这里用一个经典反例把这件事讲透。假设面额集合是 {1, 5, 6, 9}，要凑11元。贪心会先拿最大的9元，剩2元，用两张1元补上，总共3张。但最优解其实是5元加6元，只要2张。你看，贪心在这里只顾眼前拿大的，结果错失了"两个中等面额配合"的更优方案。

这个反例的意义在于提醒你：不要形成"最少硬币就用贪心"的思维定式。拿到一道新题，先判断面额有没有规整结构，再决定用贪心还是动态规划。人民币面额之所以能贪心，是因为它的面额体系经过设计，任意相邻面额之间不存在这种"配合更优"的空隙。换成游戏币、外币或者虚构面额，就要多留个心眼。

5.2 动态规划：面额乱来也不怕的后手

当贪心不可靠时，动态规划是最稳妥的办法。思路是维护一个数组 dp，dp[i] 表示凑出金额 i 所需的最少张数，初始时除 dp[0]=0 外其余都设成一个大数（表示暂时凑不出来）。然后从1元开始往上推，每个金额都尝试用每一种面额去凑，取张数最少的方案。

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n; cin >> n; vector<int> a = {1, 5, 6, 9}; // 就算面额不规整也能算对 const int INF = 1e9; vector<int> dp(n + 1, INF); dp[0] = 0; for (int i = 1; i <= n; i++) for (int v : a) if (i >= v && dp[i - v] + 1 < dp[i]) dp[i] = dp[i - v] + 1; cout << dp[n] << endl; return 0; }

这段代码对于 11 元、面额 {1,5,6,9} 的情况，会正确输出 2（5+6）。它比贪心的模板长一些，运行也慢一些（复杂度是金额乘以面额种数），但换来的是"面额随便改都不怕"的通用性。我个人建议：入门阶段先用贪心把这道人民币题吃透，等遇到贪心失效的题目，再回头补动态规划，这样学习路径更顺。

5.3 同类题型怎么串起来一起练

"人民币支付"其实是"最少硬币数"这一大类题的入门样板，练完它之后，可以顺着往下刷几道难度递增的变体。第一类是换面额版本，把人民币换成别的货币面额，考的还是同一套贪心，目的是让你确认自己会替换数组而不是死记代码。第二类是限制每种面额张数的版本，比如50元最多只有两张，这时候贪心就不一定成立了，得往动态规划或更复杂的搜索走。

第三类是"找零问题"，给定付款金额和实付金额，求应找零的最少张数，本质还是先算出差额再用同一套贪心。第四类是把"最少张数"换成"方案数"，问一共有多少种凑法，这就是另一个方向了，得用计数型动态规划。把这四类题连起来做，你会发现自己对"凑金额"这类问题的理解成体系了，而不是零散地记几段代码。

我个人在做完这道题之后最大的收获，是学会了先判断问题结构再选算法，而不是拿到题就往上套模板。面额规整就用贪心，图省事又高效；面额不规整就老老实实上动态规划，稳扎稳打。这个"先看结构、再定方法"的习惯，比记住任何一段代码都值钱。