企业官网建设流程全解析

在洛谷练动态规划题单的人，十有八九会撞上 P2840 纸币问题 2。这道题看上去平平无奇：给你几种面额的纸币，每种无限张，问凑出某个金额有多少种方案。可就是这么一道基础题，每次提交总能看到一群人卡在“组合数算重复”上，反复 WA 之后才恍然大悟。这篇文章就围绕这道题展开，把从读题到 AC 的全过程、背后的状态设计逻辑、循环顺序的坑都捋一遍，适合刚入坑 DP、准备系统刷题单的新手，也适合想一口气理清“完全背包求方案数”这个知识点的朋友。

1. 题目本质：这不是“数钱”，是“数方案”

1.1 先把原题转换成一句话

P2840 的题面很简洁：有 n 种纸币，第 i 种面额为 a[i]，每种纸币都有无数张，问组成 M 元一共有多少种不同的方案。最终答案需要对某个模数取模，通常是 1e9+7。

我先提醒一个容易搞混的点：题目说的是“纸币问题 2”，那“纸币问题 1”是什么？常见题库里的编号顺序是——纸币问题 1 往往只问“能否凑出 M”，或者问最少需要多少张；而纸币问题 2 专门问“方案总数”；纸币问题 3 则可能是限定张数上限的背包变体。所以这道题的核心诉求非常明确：给的是“方案数”，不是“最优张数”，也不是“存在性判断”。

1.2 方案数的语义：组合还是排列？

这是整个题目最大的隐含判断。假设你有两种纸币：1 元和 2 元，需要凑 3 元。用“1 张 1 元 + 1 张 2 元”和“1 张 2 元 + 1 张 1 元”，在现实世界里是同一种换钱方式。衣服包装、取钱顺序没有任何意义，所以题目默认“不考虑选取顺序”，即统计的组合方案数，而不是排列方案数。

这也是“纸币问题 2 ”和“爬楼梯”类题目的根本区别。爬楼梯每次走 1 步或 2 步，问走到第 3 级有多少种方法，那“1+2”和“2+1”算两种，因为动作顺序不同。纸币问题是按“面额种类”分组，只要每种面额取的数量一样，不管先取哪种，都只能算一种。如果你拿爬楼梯的思路直接套，样例可能都过不了——准确说，过得了小样例，但一旦面额种类多、金额大，就会多算一大片。

1.3 数据范围决定了算法方向

注意观察题目的限制，n 通常在几十到几百之间，M 通常在几千到几万之间。这个范围直接排除 DFS 暴搜，因为组合数的爆炸速度根本不是人能枚举的。即便是用递归 + 记忆化，也需要先想清楚状态维度；最自然的还是动态规划，复杂度 O(n * M)，百万级别完全在可接受范围内。

所以这道题本质上就是“完全背包求方案数”的模板题。背过完全背包求最大价值的同学，只需要把“取最大值”改成“累加方案数”，再小心处理循环方向，就能 AC。

2. 动态规划的设计：状态、转移和初始化

2.1 状态定义：dp[j] 表示什么

定义一维数组：

dp[j] = 凑成金额 j 的方案总数

有人会问，为什么不需要二维 dp[i][j] 表示“前 i 种纸币凑 j”的方案数？因为这里每种纸币无限张，没有张数限制，使用滚动数组完全可以压缩掉“纸币种类”那一维。但压缩之前，必须先理解二维状态下的转移逻辑，否则后面容易糊涂。

在二维版本中，设 dp[i][j] 表示使用前 i 种纸币（第 1 到第 i 种）凑出金额 j 的方案数。转移时考虑第 i 种纸币取 k 张，k 的范围是 0 到 floor(j / a[i])：

dp[i][j] = sum( dp[i-1][j - k * a[i]] ) 对所有合法 k

这个式子才是原始的“完全背包方案数”公式。一维版本是它的空间优化结果，但转移语义上必须保证：每个 dp[j] 只能在处理完一种面额后再更新，否则就会把不同排列顺序误认为不同方案。

2.2 转移方程：一维完全背包写法

按“外层循环面额，内层循环金额”的顺序更新：

for i = 1 to n: for j = a[i] to M: dp[j] = (dp[j] + dp[j - a[i]]) % MOD

初始化时：

dp[0] = 1

理由是：凑 0 元只有一种方案，就是哪张纸币都不拿。这个初始化是所有背包计数问题的起点，也是很多人忽略、导致最后答案全 0 的元凶。

2.3 为什么要先枚举面额，再枚举金额？

这可能是整道题最“要命”的细节。

如果先枚举金额，再枚举面额，写成：

for j = 1 to M: for i = 1 to n: if j >= a[i]: dp[j] += dp[j - a[i]]

你算出来的就是排列数。举个例子，面额 1 和 2，凑 3：

• 先金额后种类的方式，会得到：dp[3] = dp[2] + dp[1]（从面额1转移）+ ... 其中 dp[2] 又被拆成 dp[1]（面额1）和 dp[0]（面额2），于是“1+2”和“2+1”都被计入，结果偏大。

• 先种类后金额的方式，处理完面额 1 之后，dp[2] 已经有“两张1”这一种方案；再处理面额 2 时，dp[3] 从 dp[1] 转移过来，而 dp[1] 里只有“一张1”，不会再重复回溯出“先2后1”的分支，因为面额 2 是最后处理的，它不会回头再去组合面额 1 的新排列。

这个循环顺序不是玄学，而是“组合计数不重不漏”的关键。你可以自己拿两张扑克牌模拟一下：先规定好“按面额从小到大考虑，每个面额一次全部考虑完”，就能保证每种组合只被计算一次。

2.4 空间压缩的理解

二维到一维的过程中，内层金额必须从小到大（正序）遍历。这一点和 0/1 背包正好相反。

0/1 背包内层逆序，是为了防止同一件物品被重复使用；而完全背包允许无限取用，所以内层正序，让 dp[j] 可以利用更新后的 dp[j - a[i]]，相当于允许当前面额被多次选择。

这地方容易记串。我的记忆方法是：

• 0/1 背包：物品只能用一次，内层倒序，让更新后的大金额不会被本次循环中的小金额“污染”。
• 完全背包：物品能用无数次，内层正序，让更新后的小金额继续去更新大金额，实现“一张一张地叠加”。

在方案数问题上，正序配合“外层种类”的约束，恰好同时满足了“无限使用”和“不考虑顺序”两个条件。

3. 代码实现与手把手解析

3.1 核心 C++ 代码

下面这份代码可以直接作为模板，注释里写清楚了每一步的含义。

#include <bits/stdc++.h> using namespace std; const int MOD = 1000000007; const int MAXN = 1005; const int MAXM = 10005; int a[MAXN]; int dp[MAXM]; int main() { ios::sync_with_stdio(false); cin.tie(0); int n, M; cin >> n >> M; for (int i = 1; i <= n; i++) { cin >> a[i]; } dp[0] = 1; // 凑 0 元：什么都不拿 for (int i = 1; i <= n; i++) { for (int j = a[i]; j <= M; j++) { dp[j] = (dp[j] + dp[j - a[i]]) % MOD; } } cout << dp[M] << '\n'; return 0; }

3.2 每一步的意图解释

首先，用ios::sync_with_stdio(false); cin.tie(0);关掉流同步。M 最大一万左右，其实不关也能过，但这是竞赛习惯，留着没坏处。

然后读入纸币种类数和目标金额。注意这里我叫它 M，题目里可能用 m 或 other 变量名，看题面命名，避免跟数组名冲突。

dp 数组开多大？我习惯开成MAXM，比 M 最大值再大几十，防止边界访问越界。你也可以用 vector 动态分配，但静态数组更快更稳。

初始化dp[0] = 1：含义是一个空组合。很多初学者把 dp 数组初始化为 0，然后发现 dp[M] 永远是 0，就是因为少了这一步。为什么不把 dp[0] 设成 0？从状态定义看，凑 0 元确实只有“一张都不拿”这一种方案，所以是 1。从转移推导看，如果没有这一项，所有 dp[j] 在第一次处理面额时都由 dp[0] 起步，这一项缺失等于整个转移链断掉。

接下来两层循环。外层 i 表示“当前正在考虑第 i 种面额”，内层 j 从 a[i] 到 M。内层起点设为 a[i] 是因为 j < a[i] 时不可能使用当前面额，直接跳过，属于小优化。

更新时取模。如果不用模，dp 在 M 较小时可能不爆，但题目明确要求取模，所以每加一次就取一次模，安全。也可以写成：

dp[j] += dp[j - a[i]]; if (dp[j] >= MOD) dp[j] -= MOD;

因为加法最多两个小于 MOD 的数相加，不会超过 2e9+14，用 int 也可能溢出（int 上限约 2.147e9），所以要么用 long long，要么用上面的减法取模。我给出的(dp[j] + dp[j-a[i]]) % MOD会先做 int 加法，可能溢出，在某些环境下会出错。所以更稳妥的写法是：

dp[j] = (1LL * dp[j] + dp[j - a[i]]) % MOD;

强制转 long long 再做模，或者干脆把 dp 数组声明成long long。这是很多人在数值范围上踩的隐性坑，后面会详细说。

3.3 一个小优化：内层起点能不能更小？

如果当前面额 a[i] 很大，比如 10000，而 M 只有 10000，内层循环只执行一次，无所谓。但如果面额五花八门，可以考虑跳过无用的面额：如果 a[i] > M，这张纸永远用不上，直接 continue。不过这属于锦上添花，不影响正确性。

3.4 用 Python 写同样逻辑更直观

很多新手用 Python 刷题，我也顺带给出等价写法：

MOD = 10**9 + 7 n, M = map(int, input().split()) a = list(map(int, input().split())) dp = [0] * (M + 1) dp[0] = 1 for x in a: for j in range(x, M + 1): dp[j] = (dp[j] + dp[j - x]) % MOD print(dp[M])

这个写法逻辑一模一样，只是语言层面的区别。Python 的列表索引和切片天然适合这种循环，但需要注意 Python 的取模在数值较大时稍微慢一点，本题的数据范围完全没问题。

3.5 与标准完全背包最大价值的对比

如果你已经会了完全背包模板：

for i = 1 to n: for j = a[i] to M: dp[j] = max(dp[j], dp[j - a[i]] + v[i])

你会发现计数版本仅仅是把max换成+，把初始化的dp[0]=0换成dp[0]=1。这个相似性不是巧合，而是同一个状态定义下的两种度量：一个是“价值最大”，一个是“方案总数”。理解这一点后，你以后遇到“最少张数”“最多方案数”“能否凑成”都能在同一套框架里快速迁移。

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

4.1 内层循环顺序写反，结果比样例大

这是最经典的错误。面额 1、2，凑 3，正确结果应该是 2 种（1+1+1 和 1+2），如果写成先金额后面额，会算出 3 种（多一个 2+1）。排查方法非常简单：打表输出 dp[0..M]，看中间过程。

我一般会在出问题时加一段调试代码：

for (int j = 0; j <= M; j++) { cerr << dp[j] << " "; } cerr << "\n";

观察 dp[2] 在处理完面额 1 之后的值，以及处理完面额 2 之后的值。如果发现 dp 的增长轨迹有“回头”的迹象，基本就是循环顺序错了。

4.2 模数取错或忘记取模

题目如果要求模 1e9+7，你取模时写成 1000000007 没错；但有人会把模数写成 1000000009，或者 998244353，这个是题目里给定的，照着来。忘记取模的话，M 到 10000、面额多时，方案数会呈指数级膨胀，long long 都扛不住，最后 WA 或者 RE（溢出后变负数）。稳妥做法是 dp 数组直接用 long long，每处更新用(dp[j] + dp[j - a[i]]) % MOD，输出时再转 int 也没问题。

4.3 面额列表里有重复值，需要去重吗？

这是个很值得聊的隐蔽点。假如两种不同纸币面额相同，比如两种 5 元面额，题目把它们算作不同种类还是同一种？看题面描述。如果它说“n 种纸币，面值为 a[i]”，通常意味着这 n 个值本身可能不同；但如果输入出现两个相同的 a[i]，按常理这是一模一样的两种纸币，组合数不应该因此增多。

不过很多出题人不会故意塞重复面额给你添乱。如果你不放心，可以先排序去重：

sort(a + 1, a + n + 1); int cnt = unique(a + 1, a + n + 1) - (a + 1); n = cnt;

这样保证了每种面额只考虑一次，逻辑更严谨。但注意：如果题目把“种类”定义为不同编号，哪怕面额相同也算不同种，那就不能随便去重。出题人一般不会搞这种反直觉设定，请以原题面为准。

4.4 金额 M 很大，dp 数组开不下怎么办？

如果 M 上亿，二维肯定不可能，一维数组也吃紧。这种时候要看是不是要改成其他算法，比如生成函数、离散化、数论优化等。但 P2840 的数据范围就是给一维 DP 用的，不必自己吓自己。

4.5 遇到“多组输入”的情况

有些题会重复输入多组 n 和 M。如果题目要求多组数据，务必记得每组重新初始化 dp 数组，尤其是 dp[0] 重新置 1，其余位置清零。用memset(dp, 0, sizeof(dp));或者fill(dp, dp + M + 1, 0);都行，别留着上一组的数据。

4.6 方案数很大，答案全 0？

如果你输出的 dp[M] 一直是 0，先检查输入有没有读对。然后检查 dp[0] 是否初始化为 1。我给一个真实案例：有个朋友把 dp[0] 初始化成 0，理由是“0 元不用凑，所以是 0 种方案”。这个理解看似合理，但转移全靠 dp[0] 起步，一旦它是 0，整个车厢就没法动了。把 dp[0] 理解成“从起点出发的基准状态”更容易接受，它代表一种空集组合。

4.7 把“每种纸币无限张”理解成“每种只能选一次”

如果用 0/1 背包的方式去解，即内层循环倒序，你会得到一个错误但又不是完全离谱的答案：每种纸币最多用一次。当面额列表里有 1 和 2，凑 3 时，0/1 背包会得到 0 种方案（因为 1+2 允许，但 1 被用过就不能再用，2 也用完，不可能凑出 3；除非再来一张 1）。答案明显不对。记住 P2840 是“无限张”，必须完全背包正序。

5. 从一道题看开去：这题背后的知识体系

5.1 完全背包“计数”在竞赛中的变形

等你 AC 了 P2840，把目光放大一点：这类题会延伸出很多花式考法。

• 纸币问题 3：每种纸币有数量上限，这时内层要多加一层枚举张数，或者用二进制拆分 + 0/1 背包。
• 硬币找零：问凑出 M 的最小硬币数，把+换回min。
• 方案数带限制：比如不能使用某种面额，或至少使用某种面额，本质是对状态做单点禁用或偏移。
• 高精度下的大数方案数：M 不大但结果超过 64 位，可能要求用高精度或 BigInt，这时思路不变，只是实现麻烦。

因此，P2840 的价值不是让你背一道代码，而是让你彻底理解“计数 DP 的顺序与状态设计之间的关系”。以后见到“不同方案”“方案总数”“mod x”这些字样，第一反应就该想到计数背包，而不再是暴力搜索。

5.2 动态规划中的“无后效性”在这道题里如何体现

题目里每种面额可以无限选，但我们在设计状态时，并没有记录“当前还剩下哪些面额可用”，因为我们规定：只按面额种类顺序推进。当外层循环走到第 i 种面额时，未来只会使用第 i 种以及后面的面额，不会回头去用第 i-1 种。这就是无后效性：当前状态 dp[j] 已经包含了“前 i-1 种面额的全部方案”，之后转移不再关心具体是哪些组合达成的，只关心金额 j 本身。

这种“只关心当前，不管历史”的视角，是所有 DP 进阶的基石。你如果能把这一步想透，后续区间 DP、树上 DP、状压 DP 都能顺很多。

5.3 如何验证你的 DP 是否正确

除了提交 AC，自己也要学会验证。小数据可以直接手算或者暴力枚举验证。比如现有一个 n=3, M=100 的测试，你可以用递归枚举出所有组合数，再和 DP 结果对拍。对拍是竞赛里最直接的信心来源。

一个简单的验证思路：面额只有 5 和 10，凑 100。因为 5 可以凑所有 5 的倍数，组合方式无非是“用多少张 10 + 剩余的用 5 补”，所以方案数是 11（0 张 10、1 张 10、...、10 张 10）。你用上面的代码跑一下，看是不是 11。如果不是，说明某个环节还没吃透。

6. 实操中的几点个人体会

6.1 写计数 DP 时要“慢”，不要急

AC 率高的选手面对这类题，往往不是靠手速，而是靠严格的步骤：先确认“方案”的语义，再定状态，再写转移，最后才写代码。我见过很多人大脑里还没分清“组合”和“排列”，就开始敲循环，结果调试时间反而比认真想一分钟更久。

6.2 建议自己造几组极小的测试数据

不要只依赖样例。我常用的一组手工测试：

• 输入只有一种面额 3，M=6，那么方案数只有 1 种（两张 3 元），因为不存在其他面额，也不能用别的组合。
• 输入面额 1 和 3，M=3，方案数是 2 种（三张 1 元，一张 3 元）。
• 输入面额 2 和 4，M=5，方案数是 0 种，因为 5 凑不出来。

这些极限数据能快速暴露你初始化和循环方向的错误。

6.3 把“滚动数组”的更新顺序画成图

拿张纸，写下 dp[0] 到 dp[M]，然后用箭头标出每个 dp[j] 从哪个位置转移过来。处理完一种面额后，再画一次。你会发现，正序循环的箭头始终向右延伸，而每一种面额只会在自己的“层”内更新。这张图比看十遍代码都更有用。

6.4 关于取模的写法，我最终选择 long long

实际刷题时，我喜欢把 dp 数组定义成 long long，更新直接写：

dp[j] += dp[j - a[i]]; if (dp[j] >= MOD) dp[j] -= MOD;

因为 dp[j] 和 dp[j - a[i]] 都小于 MOD，加完小于 2 * MOD，减一次就够了，既快又稳。如果怕减一次不够，可以用 while，但这里是够的。这个写法在 OI 中很常见，建议记住。

6.5 什么时候用“二维数组”更安全？

如果你刚开始学，还没彻底掌握滚动数组的循环顺序，我建议先写二维版本，保证正确；AC 之后再改一维。二维状态：

vector<vector<long long>> dp(n + 1, vector<long long>(M + 1, 0)); dp[0][0] = 1; for (int i = 1; i <= n; i++) { for (int j = 0; j <= M; j++) { dp[i][j] = dp[i-1][j]; // 不选第 i 种 if (j >= a[i]) { dp[i][j] += dp[i][j - a[i]]; // 至少选一张第 i 种 } } }

注意这里“至少选一张第 i 种”用的是同一层的 dp[i][j - a[i]]，而不是 dp[i-1][j - a[i]]。这个转移的背后逻辑是：我们允许当前面额连续用多次，所以要从“已经选了当前面额”的状态再叠加。这个写法和“多重背包”区分开来，是完全背包二维形式的精髓。

二维的好处是转移语义直白，不怕循环顺序写错。缺点是空间 O(n * M)，在 n=1000、M=10000 时是 1000 万，long long 要 80MB，可能超内存。所以竞赛里最终还是推荐一维滚动数组。

6.6 别忽视“无解”情况

如果所有面额的最大公约数不整除 M，那必然凑不出 M，方案数为 0。DP 不会出错，它会自然输出 0。只是要理解，不是所有金额都能被任意凑出，这也解释了为什么用 GCD 可以提前预判一些极端大数据。不过 P2840 里你不用特意写判断，DP 自然会处理。

7. 写在最后的经验之谈

做这道题时，我自己最初也犯过“先金额后种类”的错误，当时 debug 了很久，最后输出错误结果让我百思不得其解。后来我把“组合”和“排列”这两个概念在纸面上反复推演，才意识到顺序的意义。从那之后，我养成了习惯：任何计数 DP 题，第一步先问“方案的定义是否区分顺序”，再决定循环结构。这个习惯帮我避开了无数后续的坑。

另外，如果你准备打比赛，推荐把 P2840 作为“完全背包计数”的基准模板，把它和 0/1 背包计数、多重背包计数放在一起对比学习。三种背包的代码只有微小差别，但背后的数学模型完全不同。熟练之后，你遇到“兑换零钱”“邮票组合”这类问题，基本一眼就能拆解出状态设计。

最后再分享一个小技巧：遇到这类题，先写一个递归暴搜验证函数，再写 DP，用随机小数据对拍一遍，放心程度直接翻倍。特别是当你修改了循环顺序、取模策略后，对拍能让你少提交好几次 WA。我的经验是，宁可多花三分钟对拍，也不要在评测记录里浪费几个罚时。