刷入门算法题单的时候编号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 余 3850元一张都不用剩38元38 除以 20商 1 余 1820元拿1张剩18元18 除以 10商 1 余 810元拿1张剩8元8 除以 5商 1 余 35元拿1张剩3元3 除以 1商 3 余 01元拿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输入 1000100元拿10张其余全0输出10输入 99100元和50元都是0张20元拿4张剩1910元拿1张剩95元拿1张剩41元拿4张总共411410张。这几个边界值建议都手动跑一遍比只看代码靠谱得多。3.4 写成通用模板方便日后复用把这套逻辑抽象一下就得到一个能处理任意规范面额集合的通用模板。#include iostream #include vector using namespace std; int main() { int n; cin n; vectorint 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 高频错误速查表我把这些年在这道题以及同类题上见过的错误整理成一张表出问题时对着排查能省下大量时间。现象可能原因修正方向输出等于输入的金额本身面额数组顺序写反从1元开始贪心把数组改成从大到小排列输出带小数或奇怪数值用了浮点除法而非整除C 用 int 运算Python 用 //各面额张数整体错位先更新余额再输出张数改成先输出再取模结果比预期大很多忘了取模重复计算已覆盖金额每轮结束补上 n % v分面额输出缺行用到了判断跳过0张的逻辑题目若要求六行则必须输出0占位大金额时结果不对计数器类型太小或除法溢出视范围改用 long long表格里第一条和第四条是新手最高频的错误前者结果看起来像那么回事但完全错后者往往会让张数爆炸式偏大。记住这两条能挡掉一大半问题。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 动态规划面额乱来也不怕的后手当贪心不可靠时动态规划是最稳妥的办法。思路是维护一个数组 dpdp[i] 表示凑出金额 i 所需的最少张数初始时除 dp[0]0 外其余都设成一个大数表示暂时凑不出来。然后从1元开始往上推每个金额都尝试用每一种面额去凑取张数最少的方案。#include iostream #include vector #include algorithm using namespace std; int main() { int n; cin n; vectorint a {1, 5, 6, 9}; // 就算面额不规整也能算对 const int INF 1e9; vectorint 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} 的情况会正确输出 256。它比贪心的模板长一些运行也慢一些复杂度是金额乘以面额种数但换来的是面额随便改都不怕的通用性。我个人建议入门阶段先用贪心把这道人民币题吃透等遇到贪心失效的题目再回头补动态规划这样学习路径更顺。5.3 同类题型怎么串起来一起练人民币支付其实是最少硬币数这一大类题的入门样板练完它之后可以顺着往下刷几道难度递增的变体。第一类是换面额版本把人民币换成别的货币面额考的还是同一套贪心目的是让你确认自己会替换数组而不是死记代码。第二类是限制每种面额张数的版本比如50元最多只有两张这时候贪心就不一定成立了得往动态规划或更复杂的搜索走。第三类是找零问题给定付款金额和实付金额求应找零的最少张数本质还是先算出差额再用同一套贪心。第四类是把最少张数换成方案数问一共有多少种凑法这就是另一个方向了得用计数型动态规划。把这四类题连起来做你会发现自己对凑金额这类问题的理解成体系了而不是零散地记几段代码。我个人在做完这道题之后最大的收获是学会了先判断问题结构再选算法而不是拿到题就往上套模板。面额规整就用贪心图省事又高效面额不规整就老老实实上动态规划稳扎稳打。这个先看结构、再定方法的习惯比记住任何一段代码都值钱。