洛谷P2840纸币问题2：完全背包求方案数的动态规划详解

1. 先看懂题目在问什么

1.1 题目大意与核心考点

洛谷 P2840 纸币问题 2，说人话就是：你有 n 种面额的纸币，每种面额都有无限多张，问凑出面额 m 一共有多少种不同的方案。这个“方案”是组合意义上的方案，不是排列。举个例子，面额有 1 元和 2 元，要凑 4 元，那么：

• 2 + 2
• 2 + 1 + 1
• 1 + 1 + 1 + 1

一共 3 种。注意 2 + 1 + 1 和 1 + 2 + 1 在这里算同一种，因为纸币的种类组合一样，顺序无关。这道题所有坑里，这个“算重”的问题排第一，我身边至少有一半的人第一次写会栽在这里。

这道题在洛谷动态规划题单里的位置非常靠前，属于那种“模板味道”很浓的题。它考的不是你会不会用某个冷门算法，而是你能不能看懂“完全背包求方案数”这个模型。理解它之后，很多同类题，比如换零钱、硬币组合、凑数类DP，都能顺带解决。适合的读者是刚接触DP没多久、想搞懂背包问题的同学，也适合准备蓝桥杯、CSP 这类比赛的人用来复习基础。

1.2 数据范围决定了你用什么思路

原题的数据范围我记得是 n 在 10^3 左右，m 在 10^4 级别，具体以题目页面为准。但不管具体数字是多少，这个量级已经足够说明问题：不能用暴力枚举，更不能想“我用组合数学公式直接算”。

为什么不能直接套公式？因为这是“凑数”问题，每种面额使用的张数范围是 0 到 m/a[i]，而且多种面额之间互相约束，你很难用一个封闭表达式把方案数算出来。就算用母函数硬展开，那个式子展开完也就是变相的DP，还不如一开始就老老实实做状态转移。

真正合适的方法就是动态规划。m 是背包容量，n 种面额就是 n 种物品，每种物品可以取无限次。这不就是完全背包吗？只不过把“求最大价值”换成了“求方案数”。所以这一题的实质就是把完全背包的模板改一下，把max换成累加，边界条件想清楚，就结束了。

2. 从暴力递归一步步推到动态规划

2.1 暴力DFS：能写，但会超时

如果你没学过DP，第一反应肯定是搜索。思路大概是这样：定义一个函数dfs(remain)，表示当前还差 remain 元没有凑，然后枚举下一张纸币的面额继续递归。这个方法写起来很顺畅，但有个致命问题：算重。

比如面额 1 和 2，凑 3 元。你从 1 开始能走到 1+2，从 2 开始也能走到 2+1。但题目里这俩是同一个方案。所以直接这样搜，答案会变成 2 而不是 1。

解决办法也简单，给搜索加一个“顺序约束”：递归参数里记录当前允许使用的面额下标 pos，规定下一张纸币的面额下标不能小于 pos。也就是说，我一旦选了第 3 种面额，后面就只能选第 3 种及以后的面额，不能再回头选第 1、2 种。这样每种方案只会被统计一次，因为每种方案里的纸币可以按面额下标从小到大排序，而这个排序是唯一的。

写成伪代码大概是：

void dfs(int pos, int remain) { if (remain == 0) { ans++; return; } for (int i = pos; i <= n; i++) { if (remain >= a[i]) dfs(i, remain - a[i]); } }

这个写法不重不漏，但复杂度是爆炸的，因为对于每个 remain，你都要把 i 从 pos 到 n 枚举一遍，状态没有复用。n 到 1000、m 到 10000 的时候，跑起来就是灾难。

2.2 记忆化搜索：同一个子问题只算一次

暴力DFS慢在哪？慢在同一个(pos, remain)状态被反复进入。比如你用两种不同的路径走到了“当前只能选第 2 种之后的面额，还差 5 元”这个状态，后面完全一样，却要算两次。

这给了我们一个优化方向：把(pos, remain)对应的答案记下来，下次再遇到直接读取。这就是记忆化搜索，本质上已经是自顶向下的动态规划了。

定义f[pos][remain]表示“当前允许使用第 pos 到第 n 种纸币，凑出 remain 元的方案数”。转移就是枚举下一张选哪种面额，把子问题答案相加。写出来和 DP 是一样的，只是递归实现。它的时间复杂度也降到 O(n*m) 级别，理论上是能过的。

不过，竞赛里大家更习惯写递推，因为递推不需要额外担心递归栈深度和函数调用开销，而且后面优化成一维数组也更自然。

2.3 把“按面额种类”放进状态里

很多时候初学者卡在不知道 DP 状态该长什么样。这里我提供一个很自然的思考路径：不要从“我还剩多少钱”出发，而是从“我已经考虑了哪几种面额”出发。

定义dp[i][j]表示：用前 i 种面额，恰好凑出 j 元的方案数。那么dp[n][m]就是答案。这个定义的好处是，它天然包含了“顺序无关”，因为面额的种类是一个集合，我们按顺序逐个把面额加入考虑，从第 1 种到第 i 种，从不打乱。

初始状态是dp[0][0] = 1，也就是不用任何纸币凑 0 元，这是一种方案。dp[0][j]在 j 大于 0 时全部是 0，因为不用纸币凑不出正数。

这个状态设计可以说是整个题目的灵魂。后面所有优化，都是在维持这个语义的前提下进行的。

3. 状态设计与转移方程，真正关键的部分

3.1 用手推理解状态转移

先别急着抄代码，我们用手推一遍 n=2，面额分别是 1 和 2，m=4 的情况。

dp[0]这一行：dp[0][0]=1，其他都是 0。

处理第 1 种面额（1 元）时，因为 1 元可以无限取，所以凑出任意 j 元的方案数都是 1，也就是全用 1 元。于是dp[1][j] = 1，j 从 0 到 4。

处理第 2 种面额（2 元）时，dp[2][j]等于“不用 2 元只靠 1 元凑 j”的方案数，加上“用一张 2 元后，剩下的 j-2 元继续用前 2 种面额凑”的方案数。前者是dp[1][j]，后者是dp[2][j-2]。

于是dp[2][2] = dp[1][2] + dp[2][0] = 1 + 1 = 2，对应 1+1 和 2 两种。dp[2][3] = dp[1][3] + dp[2][1] = 1 + 0 = 1，对应 1+1+1（注意 1+2 因为顺序约束不存在，算重问题消失了）。dp[2][4] = dp[1][4] + dp[2][2] = 1 + 2 = 3，和最开始手数的结果一致。

3.2 从前 i 种推前 i 种的转移方程

第 3.1 小节的递推核心就一句话：

dp[i][j] = dp[i-1][j] + dp[i][j - a[i]]

其中a[i]是第 i 种纸币的面额，前提是j >= a[i]；如果j < a[i]，那dp[i][j] = dp[i-1][j]。

这个方程的直观解释是：要凑出 j 元，第 i 种面额有两种命运——一张都不用，那就是dp[i-1][j]；至少用一张，那我先拿出一张面额 a[i]，剩下的 j-a[i] 元仍然可以由前 i 种面额来凑，也就是dp[i][j - a[i]]。因为第 i 种面额是无限的，所以“剩下的”依然放在“前 i 种”这个集合里，而不是“前 i-1 种”。

为什么这么写不会算重？因为对于任何一种确定的方案，第 i 种面额的使用张数是唯一的：用 0 张就归入第一项，用 k 张（k≥1）就归入第二项。每个方案只被划分一次。

3.3 从“枚举用几张”优化到 O(1) 转移

有些教材喜欢先写一个朴素的转移：枚举第 i 种纸币用 k 张，然后有：

dp[i][j] = sum_{k>=0} dp[i-1][j - k * a[i]]

这个式子是对的，但三重循环是 O(nmm/a[i])，跑不动。我们需要消掉枚举 k 的部分。

观察一下dp[i][j - a[i]]展开是什么：

dp[i][j - a[i]] = dp[i-1][j - a[i]] + dp[i-1][j - 2*a[i]] + dp[i-1][j - 3*a[i]] + ...

而dp[i][j]展开是：

dp[i][j] = dp[i-1][j] + dp[i-1][j - a[i]] + dp[i-1][j - 2*a[i]] + ...

对比两个式子，第二个等于dp[i-1][j] + dp[i][j - a[i]]。这就是 3.2 小节的转移方程的来历。它把枚举 k 的循环压缩成了 O(1) 的加法，这就是完全背包优化的本质。

3.4 空间优化：滚动数组和一维写法

有了二维方程之后，空间优化就很自然了。观察dp[i][j]只依赖dp[i-1][j]和dp[i][j - a[i]]。前者是上一行的值，后者是本行刚更新的值。如果我们用一个一维数组f[j]来滚动存储，那么：

• 当循环 j 从小到大递增时，f[j - a[i]]已经是当前这一轮 i 更新过的值，恰好就是dp[i][j - a[i]]；
• f[j]在更新前还是上一轮dp[i-1][j]的值。

于是：

f[0] = 1; for (int i = 1; i <= n; i++) { for (int j = a[i]; j <= m; j++) { f[j] += f[j - a[i]]; } }

关键点就在第二个循环的方向。如果是j从m往a[i]倒着循环，那f[j - a[i]]还是上一轮的值，就变成 01 背包了。从小到大循环，才允许同一种面额被反复取用。这个细节值得刻在脑子里，因为它能把 01 背包和完全背包分得明明白白。

3.5 为什么这个题不能按“排列”来算

我最初学这个题的时候有一个误区：既然纸币无限，那我每次都能从 n 种面额里任选一张，方案数难道不是每个金额的“排列”数吗？比如 f[j] = sum(f[j - a[i]])，从后往前推一步？

这个递推看起来也很合理，但它算的是排列，不是组合。因为它把一个方案里的纸币顺序区分开来了。比如凑 4，面额 1 和 2，这个递推会把 1+1+2、1+2+1、2+1+1 算成三个方案，答案变成 5，而题目要的是 3。

要避免这个问题，就必须把“面额种类”作为状态的一维，按顺序处理面额，而不是只按金额处理。这也是为什么我强调dp[i][j]的定义里必须有“前 i 种面额”这个概念。理解了这个，你就不会在看到别人代码时觉得“为什么多了一层循环”。

4. 完整实现与每一句代码的含义

4.1 参照代码（C++）

下面代码按洛谷常见数据范围和取模 1e9+7 来写，如果你的题目不需要取模，把取模删掉即可。

#include <bits/stdc++.h> using namespace std; const int MAXM = 100005; const long long MOD = 1000000007LL; int a[1005]; long long 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; for (int i = 1; i <= n; i++) { for (int j = a[i]; j <= m; j++) { dp[j] += dp[j - a[i]]; if (dp[j] >= MOD) dp[j] -= MOD; } } cout << dp[m] << "\n"; return 0; }

4.2 逐段拆解

读入部分没什么好说，面额数组 a 从下标 1 开始存，方便和状态里的“第 i 种面额”对上号。

dp[0] = 1是整个 DP 的地基。它表示“用 0 张纸币凑 0 元”这一种空方案。很多初学者在这里写 0，然后答案永远不对。记住：求方案数的 DP，初始状态几乎必然有一个dp[0]=1，代表什么都不选也是一种选择。

两层循环是核心。外层遍历 n 种面额，内层从a[i]到m正序遍历。内层循环起点是a[i]，因为金额小于a[i]时根本没法用第 i 种面额，dp[j]保持上一轮的值就行，不需要进循环。终点是 m，因为只关心凑出不超过 m 的结果。

取模这里我用了“加一次就判断一次”的方式，而不是最后才取模。原因是方案数增长极快，指数级别的数字早就超出甚至溢出 long long，必须及时取模。if (dp[j] >= MOD) dp[j] -= MOD这种写法比dp[j] %= MOD快一点，因为两个小于 MOD 的数相加不会超过 2*MOD，减一次就够了。

4.3 复杂度分析与内存

时间复杂度是 O(nm)，外层 n 次，内层 m 次，完全背包的一维优化已经把“枚举每种面额用几张”的额外开销消掉了。空间复杂度是 O(m)，只用了一个一维数组，比二维写法省下 nm 的内存。

n 取 1000、m 取 10000 时，核心操作是一千万次加法，在 OI 机上跑完就是毫秒级，完全不用担心。如果题目把 m 加到 10^6，一维写法依然能跑，但要注意数组开到够大，以及取模带来的常数开销。

4.4 如果题目要求输出字典序或具体方案

有些变种题问“把具体方案列出来”，那就不能只记方案数了。你需要在转移时额外记录每个状态是由哪个转移来的，比如pre[i][j]记录上一次选的纸币下标，然后从dp[n][m]倒推回去。这个做法的本质是 DP 表被保留下来，所以空间也回到 O(n*m)。P2840 原题只要方案数，不需要回溯，但知道这个扩展对后面做题有好处。

5. 新手最容易踩的坑，都给你列出来

5.1 一维数组顺序写反，答案莫名变大

这是完全背包和 01 背包的经典分水岭。如果你把内层循环写成for (int j = m; j >= a[i]; j--)，那dp[j - a[i]]用的是上一轮的旧值，意思是“每种面额只能选一次”，这就是 01 背包的方案数统计。测试样例可能碰巧也对，因为小数据下两种写法差别不大，但数据一大就会错。

我的建议是：不要死记“完全背包正序、01背包倒序”，而是亲手把一组小数据从二维递推展开一遍，观察一维数组的覆盖过程。当你亲眼看到dp[j]在正序循环中被同一个 i 反复更新时，就永远不会忘了。

5.2 忘记初始化dp[0] = 1

这个问题出现频率高到离谱。dp[0] = 1这个初始值是所有方案数的种子。没了它，整个 DP 表全是 0，输出也是 0。我在给别人讲题时甚至开玩笑说，所有 DP 起步第一步先想“什么都不干的情况下，我处在什么状态”。

5.3 面额有重复但没有处理

如果原题保证面额互不相同，那没问题。但如果你在做扩展题或者自己出数据验证，面额重复会让方案数虚高。假设你写了两个面额都是 2 的条目，那么“用一张 2 元”这个行为会被计入两次。

处理办法很简单：读入时用一个标记数组去重，或者排序后跳过相同值。去重不会漏掉任何真正不同的方案，因为重复面额在组合意义上没有任何额外作用。

5.4 与纸币问题 1、3 一起看对比

洛谷纸币问题是一个系列，刚好把这个系列拿出来对比，比单看一题清楚得多。纸币问题 1 是每种纸币只有一张，对应 01 背包求方案数；纸币问题 2 是每种无限张，对应完全背包；纸币问题 3 我记得是每种有限张，对应多重背包。

这样记起来很顺：循环方向决定了能不能重复拿同一个面额。

5.5 取模题和无限大数题要分开处理

P2840 这类竞赛题一般会让你对1e9+7取模，代码里取模就完事。如果哪天遇到一个不加模数的“凑方案数”题，比如让你手算小数据，你要意识到方案数可以大得离谱，几十元面额就能让 long long 都撑不住。这种题要么用高精度，要么直接换 Python 写大整数。千万别以为 long long 万能。

6. 这套思想能用在哪里，以及刷题顺序

6.1 完全背包求方案数的真实场景

这类题不只是竞赛里的宠物，现实中也有直接对应。最典型的就是“零钱兑换”：给定硬币面额，问凑成某个金额有多少种换法。LeetCode 上的 Coin Change 2 就是这道题的英文版，只是数据范围略小。还有一个常见变种是“爬楼梯升级版”，每次可以跨 1 级或 2 级，问你到第 n 级有多少种走法——那个其实更接近排列模型，因为上楼梯的顺序是有意义的，所以在套模板前一定要先想清楚题目到底认不认顺序。

另一个变种是求“最少张数”，比如给定面额和金额，问至少用多少张纸币才能凑出来。这种题和方案数只差一个转移的选择逻辑：方案数用累加，最少张数用min。核心的循环结构一模一样，学会一种就能套一种。

6.2 洛谷里值得跟着练的同类题

顺着动态规划题单走，我建议按这个顺序刷，难度循序渐进：

• P1048 采药：01 背包求最大价值，先搞懂一维滚动数组。
• P1616 疯狂的采药：完全背包求最大价值，和本题的模板非常接近。
• P2840 纸币问题 2：完全背包求方案数，就是本文的题。
• P1832 A+B Problem（再升级）：把质数当成“纸币面额”，问一个数能拆成多少个质数的和，本质也是完全背包方案数。
• P1164 小A点菜：01 背包求方案数的经典题，适合和本题对照。

这几道题吃透了，背包求方案数的绝大多数套路你就都见过了。

6.3 关于洛谷 OJ 的数据格式和处理习惯

有读者问过“洛谷该怎么放数据”，其实就是指标准输入输出。洛谷的评测机只认 stdin/stdout，程序直接从cin或scanf读数据，不要自己开文件读写，也不要在输出里夹杂提示文字。第一行一般是 n 和 m，第二行是 n 个面额，用空格或换行分隔都可以。写数时尤其注意数组越界：dp数组的下标最大到 m，所以数组大小至少开m+1，为保险多开一点。

我个人习惯const int MAXM = 100005;这种偏大的数组，宁可多占几KB内存，也不想在边界上翻车。数据范围小的时候，直接开一个很大的一维数组也无所谓，省心。

6.4 一个值得练习的小变形：把 m 和 n 换一下

如果你想加深理解，可以试试这道变形：如果金额 m 很小，但 n 很大，比如 n 到了 10^5，m 只有 100，你会怎么做？这时候 O(nm) 依然很快，因为 nm 还是 10^7 级别。但如果你能想到先按面额排序、去掉大于 m 的面额，就能进一步减少外层循环次数。这个优化思路在工程里很常见：先剪掉不可能用到的数据，再跑核心算法。

7. 我自己用这道题带新人的一点体会

每次我给人讲完这道题，都会让他们做一件有点“笨”的事：不用任何模板，手写一组 n=3、m=10 的小数据，把二维 DP 表完整填一遍。填完后在代码里只保留一维数组的版本，重新推一遍。这个过程只要做一次，你就再也不会混淆正序和倒序、组合和排列这两个最容易错的地方了。

还有一个小技巧：当你在一道新题里看到“无限可取”“任意张”“方案总数”这些词，先把完全背包求方案数的模板默写出来，再调整细节。很多 DP 题都是换个包装的旧模型，解题速度能快不少。

这道题虽然代码短，但它的信息密度极高：状态设计、转移优化、滚动数组、取模、边界条件，一个都没少。把它彻底啃下来，你收获的不只是 AC，而是一整套“背包求方案数”的分析方法。以后遇到任何凑数类问题，你都能一眼看出它属于哪一类。