企业官网建设流程全解析

第一次看到「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 的方案数」这个状态系统地推进下去。

这里有个很多人会忽略的点：方案数问题里，面额的顺序无关紧要。也就是 50+10 和 10+50 算同一种方案，不能重复计数。这个约束直接决定了代码里循环的嵌套顺序，写反了就会把同一组方案按不同排列数好几遍，答案直接爆炸。后面第 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 元实际跑一遍，追踪每一步的状态，你会看得特别清楚：

总张数是 1+0+0+1+1+0+1 = 4 张，方案就是 100+10+5+1。注意第 2、3 步的 cnt 是 0，因为剩下的 16 元里挺不住一张 50 或一张 20，这时候取模不变，金额继续往下传。这里就是前面说的「循环第 i 档处理时，money 已经只包含比 value[i] 面额更小的待处理部分」，逻辑闭环很干净。

再看一个边界值 0：输入 0 时，循环里每一档 cnt 都是 0，total 也是 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 只作为「增量」出现一次，且总是排在所有更小面额之后，方案里的面额自然是有序的，不会出现 10+50 和 50+10 被算两次的情况。

那如果反过来，外层是容量、内层是物品会怎样？那样对每个金额 j，我们都会重新遍历所有面额，得到的实际是「排列数」——50+10 和 10+50 会被当成两种。这就是典型的顺序敏感错误。举个具体的数：凑 5 元，用面额 1 和 2。如果外层容量内层物品，会数出 5=1+1+1+1+1、1+1+1+2、1+1+2+1、1+2+1+1、2+1+1+1、1+2+2、2+1+2、2+2+1 这 8 种（把 122 的各种排列都算了）。而正确的外层物品内层容量，只会数出 5=1+1+1+1+1、1+1+1+2、1+2+2 这 3 种。差距巨大。

我把这个对比整理成表，方便记忆：

做方案数题时，先看题目要求「组合」还是「排列」，再决定循环顺序，这一步想清楚，代码就不会写成玄学。

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 个 1；2+4 个 1；2+2+2 个 1；2+2+2（三个二元）；5+1 这 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 输入输出格式踩坑速查表

把常见格式坑整理成表，提交前对着核一遍：

这份表我基本每次做背包题都会扫一眼，尤其是前两条，命中率高得吓人。输出格式这种非算法问题，一旦踩了特别打击信心，因为它让你怀疑自己算法是不是也错了，其实往往只是少了个空格。

6. 从这道题延伸出的通用建模能力

6.1 币制问题到背包问题的映射

把这题吃透之后，你会发现它其实是一个更大的题库家族的一员。所有「用若干种单位凑出目标值」的问题，都能往这个框架上套。区别只在三个变量：单位是否可重复使用（决定完全背包还是 0/1）、求最少数量还是方案数（决定优化方向还是计数方向）、是否需要考虑顺序（决定循环嵌套）。

比如经典的「爬楼梯每次走 1 或 2 级，问走 n 级有多少种走法」，它跟人民币支付几乎是同一道题，只不过这里 1 和 2 是「步长」而不是「面额」，而且它要求的是排列数（1+2 和 2+1 算两种走法，因为迈步顺序不同）。你看，只要把循环顺序一换，同一套模板就能解另一道题。再比如「整数拆分」「邮票组合」「硬币找零」这些题，本质都是同一个背包模型的不同外衣。

我个人的经验是，遇到这类题先别急着写代码，先在纸上画个表格，把「单位集合、目标值、是否可重用、求数量还是方案数、是否计顺序」这五个格子填满，填完基本就知道该套哪个模板了。这个过程练熟之后，你看到题面脑子里就能自动落到某一行模板上，速度会快很多。

6.2 同类真题迁移清单

按难度递进，我列几道可以顺着练的题，都是同一个模型的变体：

• 最少张数版本练熟后，可以做「最少硬币数」类题，把面额换成任意给定额，但要先验证币制是否规范，不规范的必须改动态规划。
• 方案数版本练熟后，可以做「整数划分」问题，把面额换成 1 到 n 的所有整数，求凑出 n 的方案数，代码骨架完全一致。
• 再进阶一点，可以做带「每种面额数量有限」的版本，那就从完全背包变成多重背包，需要考虑二进制拆分或单调队列优化，这是下一步的学习内容。
• 还有一类「求最少张数但面额不规范」的题，必须用动态规划而不是贪心，专门用来打那些「见到凑钱就贪心」的思维定式。

我建议你按这个清单一道道刷过去，每道题都刻意问自己「它和人民币支付差在哪」，把差异点记录下来。等你把这几道都做完，会发现背包这一块的地基就稳了，后面再学多重背包、分组背包、树形背包，都是在这个地基上加楼层。

最后分享一个我自己的习惯：每做完一道这类题，我都会把「循环顺序、初始化、数组类型、输出格式」这四个检查项写在代码注释里，下次写新题时直接复制这段注释当检查清单。这个方法帮我挡掉了很多低级错误，尤其是时间紧张的时候，能省下大量调试时间。做算法题就是这样，思路对了只是第一步，把细节钉死才是真正拉开差距的地方。人民币支付这道例题看似入门，但它把贪心的边界、动态规划的计数、循环顺序的敏感这几个核心概念全串起来了，值得反复回看。