1. 先看懂题目在问什么1.1 题目大意与核心考点洛谷 P2840 纸币问题 2说人话就是你有 n 种面额的纸币每种面额都有无限多张问凑出面额 m 一共有多少种不同的方案。这个“方案”是组合意义上的方案不是排列。举个例子面额有 1 元和 2 元要凑 4 元那么2 22 1 11 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 开始能走到 12从 2 开始也能走到 21。但题目里这俩是同一个方案。所以直接这样搜答案会变成 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 用手推理解状态转移先别急着抄代码我们用手推一遍 n2面额分别是 1 和 2m4 的情况。dp[0]这一行dp[0][0]1其他都是 0。处理第 1 种面额1 元时因为 1 元可以无限取所以凑出任意 j 元的方案数都是 1也就是全用 1 元。于是dp[1][j] 1j 从 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对应 11 和 2 两种。dp[2][3] dp[1][3] dp[2][1] 1 0 1对应 111注意 12 因为顺序约束不存在算重问题消失了。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_{k0} 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这个递推会把 112、121、211 算成三个方案答案变成 5而题目要的是 3。要避免这个问题就必须把“面额种类”作为状态的一维按顺序处理面额而不是只按金额处理。这也是为什么我强调dp[i][j]的定义里必须有“前 i 种面额”这个概念。理解了这个你就不会在看到别人代码时觉得“为什么多了一层循环”。4. 完整实现与每一句代码的含义4.1 参照代码C下面代码按洛谷常见数据范围和取模 1e97 来写如果你的题目不需要取模把取模删掉即可。#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 我记得是每种有限张对应多重背包。题目纸币数量背包模型内层循环方向核心转移纸币问题 1每种 1 张01 背包j 从 m 到 a[i] 倒序dp[j] dp[j-a[i]]纸币问题 2每种无限张完全背包j 从 a[i] 到 m 正序dp[j] dp[j-a[i]]纸币问题 3每种若干张多重背包二进制拆分或单调队列拆成 01 背包这样记起来很顺循环方向决定了能不能重复拿同一个面额。5.5 取模题和无限大数题要分开处理P2840 这类竞赛题一般会让你对1e97取模代码里取模就完事。如果哪天遇到一个不加模数的“凑方案数”题比如让你手算小数据你要意识到方案数可以大得离谱几十元面额就能让 long long 都撑不住。这种题要么用高精度要么直接换 Python 写大整数。千万别以为 long long 万能。6. 这套思想能用在哪里以及刷题顺序6.1 完全背包求方案数的真实场景这类题不只是竞赛里的宠物现实中也有直接对应。最典型的就是“零钱兑换”给定硬币面额问凑成某个金额有多少种换法。LeetCode 上的 Coin Change 2 就是这道题的英文版只是数据范围略小。还有一个常见变种是“爬楼梯升级版”每次可以跨 1 级或 2 级问你到第 n 级有多少种走法——那个其实更接近排列模型因为上楼梯的顺序是有意义的所以在套模板前一定要先想清楚题目到底认不认顺序。另一个变种是求“最少张数”比如给定面额和金额问至少用多少张纸币才能凑出来。这种题和方案数只差一个转移的选择逻辑方案数用累加最少张数用min。核心的循环结构一模一样学会一种就能套一种。6.2 洛谷里值得跟着练的同类题顺着动态规划题单走我建议按这个顺序刷难度循序渐进P1048 采药01 背包求最大价值先搞懂一维滚动数组。P1616 疯狂的采药完全背包求最大价值和本题的模板非常接近。P2840 纸币问题 2完全背包求方案数就是本文的题。P1832 AB Problem再升级把质数当成“纸币面额”问一个数能拆成多少个质数的和本质也是完全背包方案数。P1164 小A点菜01 背包求方案数的经典题适合和本题对照。这几道题吃透了背包求方案数的绝大多数套路你就都见过了。6.3 关于洛谷 OJ 的数据格式和处理习惯有读者问过“洛谷该怎么放数据”其实就是指标准输入输出。洛谷的评测机只认 stdin/stdout程序直接从cin或scanf读数据不要自己开文件读写也不要在输出里夹杂提示文字。第一行一般是 n 和 m第二行是 n 个面额用空格或换行分隔都可以。写数时尤其注意数组越界dp数组的下标最大到 m所以数组大小至少开m1为保险多开一点。我个人习惯const int MAXM 100005;这种偏大的数组宁可多占几KB内存也不想在边界上翻车。数据范围小的时候直接开一个很大的一维数组也无所谓省心。6.4 一个值得练习的小变形把 m 和 n 换一下如果你想加深理解可以试试这道变形如果金额 m 很小但 n 很大比如 n 到了 10^5m 只有 100你会怎么做这时候 O(nm) 依然很快因为 nm 还是 10^7 级别。但如果你能想到先按面额排序、去掉大于 m 的面额就能进一步减少外层循环次数。这个优化思路在工程里很常见先剪掉不可能用到的数据再跑核心算法。7. 我自己用这道题带新人的一点体会每次我给人讲完这道题都会让他们做一件有点“笨”的事不用任何模板手写一组 n3、m10 的小数据把二维 DP 表完整填一遍。填完后在代码里只保留一维数组的版本重新推一遍。这个过程只要做一次你就再也不会混淆正序和倒序、组合和排列这两个最容易错的地方了。还有一个小技巧当你在一道新题里看到“无限可取”“任意张”“方案总数”这些词先把完全背包求方案数的模板默写出来再调整细节。很多 DP 题都是换个包装的旧模型解题速度能快不少。这道题虽然代码短但它的信息密度极高状态设计、转移优化、滚动数组、取模、边界条件一个都没少。把它彻底啃下来你收获的不只是 AC而是一整套“背包求方案数”的分析方法。以后遇到任何凑数类问题你都能一眼看出它属于哪一类。