第一次看到「3033【例8.1】人民币支付」这个标题很多人会下意识觉得它没什么技术含量——不就是拿几张钱凑一个数字吗小学奥数都做过。但真上手写代码就会发现这道题是无数人第一次被迫掰扯清楚「贪心到底什么时候是对的、什么时候会翻车」的起点。它表面上在算钱实际在考你对币制结构、贪心选择性质、完全背包计数这几件事的理解。人民币支付这类问题核心无非两个变种给定金额求最少张数以及给定金额求有多少种不同的支付方案。前者是贪心的经典练手场后者是动态规划里完全背包的入门标本两个方向的思维差异很大但都绕不开对面额数组和循环顺序的细致处理。这篇内容适合刚接触算法竞赛、正在刷例题的新手也适合带课的老师拿去当讲解素材我会把两种解法从「为什么这么想」讲到「代码每一行在干什么」再把自己踩过的坑一条条摊开说力求看完就能直接复现。1. 从标题拆解这道人民币支付题到底在考什么1.1 题目场景还原与核心需求先把场景说清楚。题目通常给一个整数金额比如 116然后你手上有一叠理论上无限多的人民币面额固定为 1、2、5、10、20、50、100 这七种。要求你把这个金额付出去输出需要用到的纸币张数或者输出一共有多少种不同的凑法。这就是「人民币支付」最朴素的形态。别小看这个设定。现实生活中我们也确实这么干——去超市买 87 块的东西你会本能地掏一张 50、一张 20、一张 10、一张 5、一张 2而不是掏 87 张一块钱。这种「能不麻烦就不麻烦」的直觉翻译成算法语言就是在每一步都选择当前看起来最优的解也就是贪心。所以这道题对新手很友好的一点是它不需要你凭空建立抽象模型生活经验直接就能映射到算法策略上。但题目只给你生活直觉是不够的它要的是可复现、可证明、能通过所有测试点的代码。金额最小可能是 0最大可能到几千甚至上万面额组合的规模会迅速膨胀这中间就藏着不少需要提前想明白的细节0 元怎么处理如果贪心不成立怎么办如果问的是方案数答案会不会大到溢出 int这些问题不解决代码在样例上跑得漂亮一提交就红一片。从核心需求来看这道题其实在训练三种能力一是把生活问题抽象成数组遍历问题的能力二是对贪心正确性的敏感度三是对动态规划计数模型的初步搭建能力。这三种能力在后续所有算法题里都是高频复用的所以这道例题虽小覆盖面却不窄。1.2 面额体系里藏着的关键数学性质人民币面额不是随便拍的脑袋它背后有个正式概念叫「规范币制」英文是 canonical coin system。简单说就是对于这套面额贪心算法一定能给出最少张数不存在「贪心用了 3 张、最优解只要 2 张」的情况。我来给一个反例帮大家建立对比感。假设某个国家的面额是 1、3、4要付 6 元。贪心的思路是先拿最大的 4剩 2再拿两个 1总共 3 张但聪明人会直接拿两张 3只要 2 张。这就是贪心翻车的经典场景——面额之间不满足「大面额是小面额的合理倍数组合」贪心就会走岔路。而人民币的 1、2、5、10、20、50、100 这套体系恰好避开了这个坑。每一个较大的面额都能被若干小面额高效地表示且任意两次相邻面额之间的比值都不超过一个安全范围。我不是要在这里证一遍数学定理你只需要记住结论做最少张数版本用贪心是安全的可以放心大胆地从 100 元开始一路往下除。这个前提如果搞混把面额数组改一改比如出题人故意换成 1、3、4贪心就会错这点在后面排查章节我会重点再提。理解这个性质的意义在于它决定了你选哪条路。如果题目保证用的是人民币标准面额你完全可以走贪心这条又快又简单的路如果题目允许自定义面额或者问的是方案数那必须换武器。认清问题所处的「币制环境」比埋头写代码重要得多。1.3 谁适合看这篇能收获什么这篇内容我打算按两条主线铺开一条是贪心求解最少张数另一条是完全背包求方案数。新手可以从头顺着读把两种思路都吃透有一点基础的朋友可以直接跳到动态规划那节重点看循环顺序的推导那是最容易写反的地方。对正在备赛的同学来说这道题的真正价值不在于通过它而在于它引出的几个通用模式把硬币兑换、邮票组合、整数拆分这类题目全都归约到同一套模板上。你会发现很多看起来不同的题代码骨架其实是同一份区别只在细节参数和输出要求。掌握了这种归约能力你的刷题效率会有一个明显的跃升。另外我也会讲清楚循环边界的推导过程。很多人写完全背包是背模板外层物品、内层容量的正序循环抄下来能过但换个题就蒙。我会告诉你为什么内层要正序、为什么倒序就变成 0/1 背包把原理讲透你以后就不需要背了。2. 解法选型为什么大多数人第一反应是贪心2.1 贪心策略的直觉与形式化描述贪心的形式化描述其实特别干净把面额从大到小排好从 100 开始能塞几张就塞几张塞完把剩下的金额交给下一个面额一直做到 1 元。整个过程中每一步都局部最优而且一旦做了选择就绝不反悔——这就是贪心的精髓不回退。为什么这个不回退的策略在人民币上能行得通因为大面额和小面额之间存在「整数覆盖」的关系。举个例子你付 116 元用了 1 张 100 后剩 16。这 16 元如果全用 10 元来付需要 1 张 10 加 6 个一块共 7 张但你改用一张 10、一张 5、一张 1只用了 3 张补上剩下的部分。贪心并没有让你在 100 那张上纠结「是不是该换两张 50」因为它知道用一张 100 一定比两张 50 省张数。这种「大的一定比小的省」的特性在人民币面额里处处成立。所以贪心的正确性其实建立在一个朴素事实上任何用两个较小面额能拼出的金额用一个大面额搞定都不会更亏。这个性质一旦成立贪心就可以放心往下推。我经常跟新手说做这类题先问自己一句「我能不能用更大的一张替换掉手上两张小的」如果能贪心大概率就是对的方向。2.2 贪心什么时候会失效——从币制说起前面已经给了 1、3、4 面额的反例这里把失效的机理讲得更透一点。贪心失效的根源是「局部最优选择斩断了通往全局最优的路」。在面额 1、3、4 付 6 元的场景里贪心第一步拿了 4看似省了张数但它把剩余金额切成了 2而 2 只能用 1 加 1 来补总额变成 3 张。如果第一步不贪那张 4直接拿两张 3就是 2 张。贪心的错误在于它过于武断地相信「用最大的就一定最好」。判断一套币制是否支持贪心有个实用的经验判据把面额从小到大排如果每个面额都大约是前一个的 2 到 2.5 倍以内且没有出现「用一个大的反而比两个次大的更差」的组合基本就是规范币制。人民币 1→2→5→10→20→50→100相邻比值都在这个范围内是典型的规范币制。所以你在标准题里可以放心用贪心但一旦题目改面额必须重新验证不能默认成立。我踩过一次坑某次比赛题目给的「魔法币」面额是 1、4、6、9找 12贪心会拿 9 加三个 1共 4 张而最优是两张 6只有 2 张。当时我没验证币制直接套了贪心模板结果被大数据点卡住。从那以后我养成习惯——看到非标准面额先手工构造小规模反例再决定用贪心还是动态规划。2.3 什么时候必须上动态规划如果你想求的不是「最少张数」而是「一共有多少种支付方案」那贪心直接报废因为张数最少不等于方案唯一你要数的是所有可能组合而非其中最优的那个。这就是动态规划的战场。方案数问题和最少张数问题是两种不同性质的问法。最少张数是优化问题目标是找一个最优值方案数是计数问题目标是数出满足条件的解的总个数。计数问题天然不适合贪心因为你没法用「局部最优」推出「总共几种」必须老老实实把状态全部枚举并累加。这就是为什么完全背包会成为方案数版本的标准解法它能把「用前 i 种面额凑出金额 j 的方案数」这个状态系统地推进下去。这里有个很多人会忽略的点方案数问题里面额的顺序无关紧要。也就是 5010 和 1050 算同一种方案不能重复计数。这个约束直接决定了代码里循环的嵌套顺序写反了就会把同一组方案按不同排列数好几遍答案直接爆炸。后面第 4 节我会专门用一段把这件事讲清楚。3. 贪心实现最少张数支付的完整代码与逐行拆解3.1 面额数组的排列方向与循环设计先定一个基调贪心版本里面额数组一定要从大到小排也就是{100, 50, 20, 10, 5, 2, 1}。原因很简单贪心的核心动作是「优先用大面额」数组顺序决定了循环先碰谁。如果你不小心写成从小到大{1, 2, 5, ...}那循环第一次就把金额全除以 1等于直接输出「全是 1 元共 N 张」虽然数学上也是合法支付方案但绝对不是最少张数测试点会全线报错。循环设计上除了面额数组的方向还有一个隐藏细节每一轮除完之后要立刻做取模也就是money % value[i]把已经用掉的部分扣掉剩下的交给后面更小的面额处理。如果忘了取模金额不会更新后面每一档都会重复算同一个大金额结果离谱。这个取模操作和除法是一对写的时候最好贴着写别隔开。再一个容易忽略的地方是有些题目不需要你输出每种面额用几张只要你输出总张数。这时候可以省掉打印明细的那行但累加总张数的变量不能少。我建议即使题目只问总数也先把明细打印出来调试验证确认无误后再删掉这样能第一时间发现哪一档对不上。3.2 代码实现与运行过程追踪下面是贪心版本的完整代码#include iostream using namespace std; int main() { int money; int value[7] {100, 50, 20, 10, 5, 2, 1}; // 面额从大到小 cin money; int total 0; // 记录总张数 for (int i 0; i 7; i) { int cnt money / value[i]; // 当前面额能用几张 if (cnt 0) { cout value[i] 元: cnt 张 endl; } total cnt; money % value[i]; // 扣掉已用的部分 } cout 共 total 张 endl; return 0; }拿 116 元实际跑一遍追踪每一步的状态你会看得特别清楚步骤当前面额money 值cnt张数取模后 money110011611625016016320160164101616556116210171110总张数是 1001101 4 张方案就是 1001051。注意第 2、3 步的 cnt 是 0因为剩下的 16 元里挺不住一张 50 或一张 20这时候取模不变金额继续往下传。这里就是前面说的「循环第 i 档处理时money 已经只包含比 value[i] 面额更小的待处理部分」逻辑闭环很干净。再看一个边界值 0输入 0 时循环里每一档 cnt 都是 0total 也是 0最后输出「共 0 张」。这符合生活常识——0 元不用付钱。有些题可能规定金额至少为 1但从代码健壮性角度能正确处理 0 是加分项。3.3 边界与特殊输入的处理贪心版本表面简单但边界上有三个点必须盯住。第一个是金额为 0 的处理。前面说了代码天然支持不用特别写判断但如果你用了「打印每档明细」的逻辑0 元时任何明细都不打印只输出总张数 0这是对的。第二个是金额较大时的类型问题。如果题目金额上限是 1e9 甚至更大int还能扛得住因为int上限大概 21 亿。但如果上限更大比如 1e18那就必须换成long long否则读入阶段就溢出。判断方法很简单把题目给的数据范围上限看一眼超过 2e9 一律用long long别赌。第三个是输出格式。有些题目要求输出「最少需要 X 张」有些要求逐行输出每种面额用了几张、0 张的跳过有些甚至要求按面额从小到大输出。格式错一个标点都会被判错这跟算法没关系纯粹是审题仔细不仔细。我吃过这亏样例输出里带单位「张」我漏了本地自测时又用眼睛扫过去没注意提交后 WA 三次才发现。建议把题面输出要求那一段单独抄在草稿纸上写完代码逐字对照。4. 进阶支付方案数的完全背包写法4.1 状态定义与转移方程的推导现在换到方案数版本。我们要数的是「用 1、2、5、10、20、50、100 这些面额凑出金额 n一共有多少种不同组合」组合不区分顺序。设dp[j]表示凑出金额 j 的方案总数。初始状态dp[0] 1意思是「凑出 0 元有且仅有一种方式就是什么都不拿」。这个初始值很多人不理解觉得 0 元应该是 0 种方案。其实去想物理意义你面前放着一个空篮子凑 0 元的方式就是「什么都不放」这一种所以是 1不是 0。这个 1 是后面所有递推的种子如果错误地设成 0整个 dp 数组会全变 0答案永远是 0。转移方程是dp[j] dp[j] dp[j - value[i]]。它的含义是考虑当前面额 value[i] 时「凑出 j 元」的方案可以分成两类——一类是不用这个面额方案数是原来的dp[j]另一类是用至少一张这个面额那剩下的金额 j - value[i] 还要继续用当前及更小的面额凑方案数是dp[j - value[i]]。两类相加就是新的 dp[j]。这里有个关键点是完全背包和 0/1 背包的分水岭内层循环的方向。完全背包里每种面额可以用无限多张所以内层循环要正序从 value[i] 一路加到 n。这样在计算 dp[j] 时dp[j - value[i]]已经在本轮更新过了包含了「又多用一张当前面额」的情况正好对应无限使用的语义。如果写成倒序就变成了 0/1 背包每种面额只能用一次结果直接错。4.2 循环顺序为什么如此重要这是全篇最容易翻车的地方我单独拎出来讲。代码里循环有两层外层遍历面额物品内层遍历金额容量。这个顺序不能乱。外层必须是物品内层必须是容量而且内层正序。为什么外层是物品因为这决定了我们「一种面额一种面额地考虑」。当外层走到 50 时意味着前面 1、2、5、10、20 这些面额的所有组合已经全部统计完毕。此时再引入 50等价于问「在前面所有组合的基础上加入若干张 50能形成哪些新方案」。由于 50 只作为「增量」出现一次且总是排在所有更小面额之后方案里的面额自然是有序的不会出现 1050 和 5010 被算两次的情况。那如果反过来外层是容量、内层是物品会怎样那样对每个金额 j我们都会重新遍历所有面额得到的实际是「排列数」——5010 和 1050 会被当成两种。这就是典型的顺序敏感错误。举个具体的数凑 5 元用面额 1 和 2。如果外层容量内层物品会数出 511111、1112、1121、1211、2111、122、212、221 这 8 种把 122 的各种排列都算了。而正确的外层物品内层容量只会数出 511111、1112、122 这 3 种。差距巨大。我把这个对比整理成表方便记忆循环结构内层方向语义典型问题外层物品内层容量正序完全背包组合数支付方案数本题外层物品内层容量倒序0/1 背包组合数每种面额限用一次外层容量内层物品正序完全背包排列数跳台阶、上下楼梯做方案数题时先看题目要求「组合」还是「排列」再决定循环顺序这一步想清楚代码就不会写成玄学。4.3 完整代码与对拍验证方案数版本的完整代码#include iostream using namespace std; int main() { int n; int value[7] {1, 2, 5, 10, 20, 50, 100}; // 顺序在此而言不重要习惯从小到大 long long dp[100005] {0}; cin n; dp[0] 1; // 凑出 0 元有一种方式 for (int i 0; i 7; i) { for (int j value[i]; j n; j) { dp[j] dp[j - value[i]]; } } cout dp[n] endl; return 0; }这段代码里dp数组用long long是因为方案数的增长速度极其夸张。以凑 100 元为例标准面额的方案数已经是一万多种金额继续增大方案数会指数级膨胀int很容易溢出所以必须用long long。这是我强烈建议新手养成的习惯——看到计数类动态规划先别管会不会溢出直接上long long省得调试半天发现是类型问题。至于验证我常用的办法是对拍写一个暴力递归版本枚举所有面额组合去数方案数然后拿小规模数据比如 n 从 1 到 50和动态规划跑出来的结果逐一比对。如果全对说明 dp 逻辑没问题。暴力版虽然慢但作为验证器非常可靠尤其是当你不确定循环顺序写没写对时对拍能帮你快速定位。我用一个具体数验证一下。凑 6 元标准面额下方案有6 个 124 个 1222 个 1222三个二元51 这 5 种。用代码算 dp[6]结果正是 5对拍通过。你也可以自己拿纸笔数一遍感受一下「组合不计顺序」这个约束带来的人工计数难度这正是我们依赖动态规划的原因。5. 常见问题与排查技巧实录5.1 面额写错导致的隐蔽错误面额数组写错是新手最常见的失误而且错误往往很隐蔽。有的同学把 20 写成 25有的漏了 2 元那一档有的把 50 和 20 的顺序写反。这些错误在样例上不一定暴露因为样例金额经常能被现有面额凑出来只有特定测试点才会炸。我建议的做法是写完面额数组后立刻打印一遍然后心里默念对应的纸币一百、五十、二十、十、五、二、一逐个数一遍。别觉得幼稚我见过太多人因为数组里一个数字打错调了半小时没找着原因。还有个小技巧面额数组用一个常量声明并在注释里写清楚是哪些面额这样复习时一眼能看懂。如果是贪心版本的题面额顺序必须是降序如果是完全背包方案数版本顺序无所谓但从小到大写更符合直觉。你可以根据不同版本准备两份数组避免混用。5.2 大额输入的溢出与效率问题溢出问题分两个层面一是输入数据的溢出二是中间计算结果的溢出。输入溢出看数据范围。金额如果到 1e5 级别int足够了但方案数的值会非常大哪怕金额只有 1000方案数也可能冲到十亿以上必须long long。我吃过亏有次忘了改类型答案在小数据上全对一到大金额就变成负数或者乱码查了半天才回头发现是int溢出。所以习惯上涉及计数的 dp 数组一律long long输入金额视范围选int或long long。效率方面完全背包是 O(7 × n)7 是面额种数n 是金额这个复杂度非常低n 到 1e5 都毫无压力。贪心更是 O(7)几乎零开销。所以这道题不用担心超时真正要专心的是正确性。如果哪天你遇到面额种类特别多比如几千种的情况那才需要重新评估复杂度但对本题来说完全够用。5.3 输入输出格式踩坑速查表把常见格式坑整理成表提交前对着核一遍问题现象可能原因解决办法样例对提交 WA输出多/少空格、换行或漏了单位词逐字对照题面输出要求答案偏大许多循环顺序写反数成了排列数外层改物品内层改容量正序答案恒为 0dp[0]初始化错误设为 1 而非 0答案出现负数计数 dp 用了int溢出改用long long贪心结果不是最少面额非规范币制或数组方向写反验证币制数组改降序金额 0 时输出异常没处理空方案边界检查 dp[0] 和贪心循环这份表我基本每次做背包题都会扫一眼尤其是前两条命中率高得吓人。输出格式这种非算法问题一旦踩了特别打击信心因为它让你怀疑自己算法是不是也错了其实往往只是少了个空格。6. 从这道题延伸出的通用建模能力6.1 币制问题到背包问题的映射把这题吃透之后你会发现它其实是一个更大的题库家族的一员。所有「用若干种单位凑出目标值」的问题都能往这个框架上套。区别只在三个变量单位是否可重复使用决定完全背包还是 0/1、求最少数量还是方案数决定优化方向还是计数方向、是否需要考虑顺序决定循环嵌套。比如经典的「爬楼梯每次走 1 或 2 级问走 n 级有多少种走法」它跟人民币支付几乎是同一道题只不过这里 1 和 2 是「步长」而不是「面额」而且它要求的是排列数12 和 21 算两种走法因为迈步顺序不同。你看只要把循环顺序一换同一套模板就能解另一道题。再比如「整数拆分」「邮票组合」「硬币找零」这些题本质都是同一个背包模型的不同外衣。我个人的经验是遇到这类题先别急着写代码先在纸上画个表格把「单位集合、目标值、是否可重用、求数量还是方案数、是否计顺序」这五个格子填满填完基本就知道该套哪个模板了。这个过程练熟之后你看到题面脑子里就能自动落到某一行模板上速度会快很多。6.2 同类真题迁移清单按难度递进我列几道可以顺着练的题都是同一个模型的变体最少张数版本练熟后可以做「最少硬币数」类题把面额换成任意给定额但要先验证币制是否规范不规范的必须改动态规划。方案数版本练熟后可以做「整数划分」问题把面额换成 1 到 n 的所有整数求凑出 n 的方案数代码骨架完全一致。再进阶一点可以做带「每种面额数量有限」的版本那就从完全背包变成多重背包需要考虑二进制拆分或单调队列优化这是下一步的学习内容。还有一类「求最少张数但面额不规范」的题必须用动态规划而不是贪心专门用来打那些「见到凑钱就贪心」的思维定式。我建议你按这个清单一道道刷过去每道题都刻意问自己「它和人民币支付差在哪」把差异点记录下来。等你把这几道都做完会发现背包这一块的地基就稳了后面再学多重背包、分组背包、树形背包都是在这个地基上加楼层。最后分享一个我自己的习惯每做完一道这类题我都会把「循环顺序、初始化、数组类型、输出格式」这四个检查项写在代码注释里下次写新题时直接复制这段注释当检查清单。这个方法帮我挡掉了很多低级错误尤其是时间紧张的时候能省下大量调试时间。做算法题就是这样思路对了只是第一步把细节钉死才是真正拉开差距的地方。人民币支付这道例题看似入门但它把贪心的边界、动态规划的计数、循环顺序的敏感这几个核心概念全串起来了值得反复回看。