第一次在题目列表里看到“Sewing Buttons with Grandma”UVa 12316时我以为是那种讲故事送温暖的题。读完题面发现这题翻译过来就是奶奶有一堆大小不一的纽扣每一种都有无限多颗她想凑出一个指定大小的总和问一共有几种凑法。没有感情戏没有场景描写剩下的全是背包问题。得祖母再慈祥该写状态转移还是得写。这题在很多算法爱好者看来是入门级别的完全背包计数题但它有一个很容易被人忽略的坑同样是“用无限物品凑总和”循环顺序写错答案就会从组合数变成排列数WA得毫无脾气。再加上答案可能特别大很多语言自带大数但C选手就得自己手写。这篇文章我会把这道题从读题、建模、状态设计、去重技巧、大数加法到踩坑经验全部过一遍适合正在刷动态规划基础题、尤其是背包专题的同学参考。1. 题目到底在做什么先把这个“缝扣子”问题翻译成数学题1.1 题面看着温馨条件其实很硬题目背景很简单奶奶要缝一件有很多扣眼的外套身边有一个装满纽扣的盒子。盒子里有若干种尺寸的纽扣每一种都不限数量。现在给定一个目标大小 n问用这些纽扣能凑出多少种不同的方案使得所选纽扣的尺寸总和恰好等于 n。比如目标大小是 5纽扣种类有两种尺寸 2 和尺寸 3。那么可以凑出的方案只有一种23。虽然你写代码时可能是先取 2 再取 3也可能先取 3 再取 2但“拿一颗 2 和一颗 3”这件事在物理世界里是同一个结果不能当成两种方案。这就是这道题和很多初学者的直觉最容易打架的地方。题目的输出是一串数字不是取模后的余数。也就是说方案数可能非常大甚至超出 64 位整数能表示的范围。这个细节直接决定了我们后面必须处理大数。很多人在状态转移都写对的情况下栽在这一步觉得“可能很大”就是“可能超过 int”结果用 long long 一交直接溢出输出一堆乱码。1.2 输入输出和数据范围题目是多组输入常见写法是读到文件末尾结束。每一组数据先给一个正整数 n表示需要凑出的目标大小接着给一个正整数 m表示纽扣的种类数然后给 m 个整数表示每种纽扣的尺寸。[ n \le 100,\quad m \le 50 ]这是题目中隐藏的关键信息。n 只有 100说明我们完全可以开一个长度为 n1 的 dp 数组不需要任何高级优化。m 也只有 50循环嵌套没有任何压力。真正的压力全在结果数字的长度上因为组合方案数是指数级别的哪怕 n 很小方案数也可能长到几十位甚至上百位。有些版本的题目会把 n 为 0 作为终止条件有些版本不会具体以你复现时的题面为准。我下面给出的代码按“读到 EOF遇到 n0 就结束”的常见风格处理如果没有这个约定删掉 break 分支即可。1.3 为什么直接判定为完全背包计数问题判断一个题是不是背包问题就看三个要素物品、容量、选择限制。这里的物品是纽扣种类容量是目标大小 n限制是每种纽扣可以取任意多颗。所以模型非常清晰完全背包但不是求最大价值而是求方案总数。这里最容易出现的一个误区是“这不就是组合数学里的正整数拆分吗能不能用生成函数、母函数去解”理论上可以生成函数的系数就是答案但写起来比动态规划复杂而且在大数场景下没有任何优势。对 OJ 来说动态规划就是最标准、最稳妥、最好写的解法。还有一点值得提醒有些同学第一眼看到“无限取”就想到高中数学里的隔板法、整数拆分公式但库里尺寸不是从 1 到 n 的连续整数而是给定的任意正整数序列。比如可能只有尺寸 3 和尺寸 5没有 1 和 2。这种情况下整数拆分公式完全不适用必须老老实实用背包。2. 解题思路拆解从暴力枚举到动态规划2.1 暴力枚举为什么活不过两秒最朴素的想法是枚举每种纽扣取多少颗。设第 i 种纽扣取了 (c_i) 颗那么要满足[ \sum_{i1}^{m} c_i \times w_i n ]这个枚举的规模有多大最坏情况下每一种纽扣的取值都有 (O(n / w_i)) 种可能全部组合起来是乘积级别。n100m50 时即使每种尺寸都比较大暴力组合也会轻松爆炸。就算剪枝枚举过程中还涉及“判断是否重复”的问题因为纽扣组合不区分顺序枚举生成的有序组合还要再做一次去重复杂度根本不可接受。所以这题必须用动态规划。动态规划的好处是它把“用前 i 种纽扣凑某个总和”这件事做成状态通过递推避免重复计算同时天然规避了顺序问题。2.2 状态定义让“前 i 种”成为核心维度定义状态[ dp[i][j] 前 i 种纽扣凑出总大小 j 的方案数 ]其中 i 从 0 到 mj 从 0 到 n。这里“前 i 种”是严格有序的我们先把所有纽扣种类从左到右排好队考虑前 1 种、前 2 种……这样在计算时方案集合被一张“种类先后”的标签隔离永远不会把同一种组合通过不同顺序重复计入。初始化也很直观前 0 种纽扣凑出总大小 0 的方案数是 1也就是什么都不取前 0 种纽扣凑出任何大于 0 的总大小都是 0因为没有任何纽扣可用。[ dp[0][0] 1 ][ dp[0][j] 0 \quad (j 0) ]2.3 转移方程选 0 个和至少选 1 个有了状态怎么从前面的状态推到当前状态对第 i 种纽扣尺寸为 w我们有两种情况的叠加。第一完全不使用第 i 种纽扣。那么方案就是从“前 i-1 种”凑出 j[ dp[i][j] dp[i-1][j] ]第二至少使用 1 颗第 i 种纽扣。可以先拿掉一颗尺寸为 w 的纽扣剩下的 j-w 仍然允许继续使用第 i 种因为数量无限[ dp[i][j] dp[i][j-w] \quad (j \ge w) ]这里需要仔细体会为什么是 (dp[i][j-w]) 而不是 (dp[i-1][j-w])因为当我们“已经决定至少放一颗第 i 种纽扣”时剩余的 j-w 还可以再放第 i 种纽扣这是一种递归式的定义。如果写成 (dp[i-1][j-w])就只能放一颗第 i 种纽扣第二颗、第三颗都放不了那就退化成 0/1 背包了。完整的转移就是[ dp[i][j] dp[i-1][j] (j \ge w \text{ 时 } dp[i][j-w]) ]这个写法我在刚开始学的时候总觉得有点绕后来用一个生活例子理解你在自助餐厅拿菜面前有“前 i 道菜”的取餐区。要么这一轮完全跳过第 i 道菜那么方案数继承“前 i-1 道菜”的情况要么你至少夹一筷子第 i 道菜夹完之后你还可以接着夹这道菜于是问题回到“前 i 道菜”里凑 j-w 的剩余量。这样就既允许无限取又因为没有给第 i 道菜设置“排列顺序”不会把同一道菜的不同夹取顺序重复计数。2.4 一维压缩从二维表到滚动数组观察转移式(dp[i][j]) 只依赖 (dp[i-1][j]) 和 (dp[i][j-w])。前者是上一行的旧值后者是本行前面位置刚算出来的新值。所以我们可以只用一个一维数组按顺序覆盖更新。[ dp[j] dp[j] dp[j-w] \quad (j \text{ 从小到大遍历}) ]这里的内层循环顺序非常关键必须从小到大遍历 j。因为 (dp[j-w]) 在 (j) 之前已经被更新过它代表的正是同一轮内“已经使用了第 i 种纽扣”的方案数这正好对应完全背包“允许无限使用”的特性。如果改成从大到小遍历(dp[j-w]) 还是上一轮的旧值那就变成 0/1 背包每种纽扣最多用一次。这个“正序还是倒序”的细节是背包问题里的老演员了但每次考试还是有人错。我的习惯是记一句话完全背包正序0/1 背包倒序。做题前先想清楚这题是无限取还是一次取再决定方向。3. 代码实现与关键细节大数、初始化、循环顺序3.1 大数加法自己动手不用库先回答一个问题这题的方案数到底能有多大n100、m50、所有纽扣尺寸都是 1 时答案是 (2^{99}) 级别的天文数字大约 30 位十进制数。如果尺寸更小、种类更多还能更大。long long 只能存到 (9.22 \times 10^{18})连零头都不够所以必须用大数。C 在 ACM 环境下最稳妥的做法是自己写一个字符串加法。加法逻辑不难按位从低位到高位加处理进位。写一次通用函数后面所有类似“计数型背包”的题都能直接用。这里我给出一个可靠实现版本string addString(const string a, const string b) { string res; int i (int)a.size() - 1; int j (int)b.size() - 1; int carry 0; while (i 0 || j 0 || carry) { int sum carry; if (i 0) sum a[i--] - 0; if (j 0) sum b[j--] - 0; carry sum / 10; res.push_back(char(0 sum % 10)); } reverse(res.begin(), res.end()); return res; }这个函数每次生成一个新的字符串虽然会有额外开销但在 n≤100 的场景下完全足够。如果你担心多次分配字符串导致超时也可以用固定长度的 char 数组配合手写进位但一般情况下没必要。3.2 C 参考实现下面给出一个可以直接 AC 的完整实现。为了节省空间dp 数组直接开一维并且用 string 类型存储大数。首先初始化 dp 数组为全 0再把 dp[0] 设置为 1表示凑出大小为 0 的方案有一种。然后外层循环枚举纽扣种类内层循环用正序更新 dp。最终 dp[n] 就是答案。#include bits/stdc.h using namespace std; string addString(const string a, const string b) { string res; int i (int)a.size() - 1; int j (int)b.size() - 1; int carry 0; while (i 0 || j 0 || carry) { int sum carry; if (i 0) sum a[i--] - 0; if (j 0) sum b[j--] - 0; carry sum / 10; res.push_back(char(0 sum % 10)); } reverse(res.begin(), res.end()); return res; } int main() { int n; while (cin n n) { int m; cin m; vectorint w(m); for (int i 0; i m; i) { cin w[i]; } vectorstring dp(n 1, 0); dp[0] 1; for (int i 0; i m; i) { for (int j w[i]; j n; j) { dp[j] addString(dp[j], dp[j - w[i]]); } } cout dp[n] \n; } return 0; }这段代码里最需要注意的就是for (int j w[i]; j n; j)内层从 w[i] 开始从小到大走到 n。很多人在写完全背包求方案数时习惯用二维数组然后手动写三重循环枚举第 i 种取 k 个那样也能过但代码更长也更难查错。一维写法干净利落前提是理解清楚“正序更新”的含义。3.3 Python 对照享受语言红利但也别掉坑如果你平时刷题用 Python那大数问题直接消失因为 Python 的整数没有位数限制。同样的逻辑翻译成 Pythonwhile True: try: n int(input()) if n 0: break m int(input()) weights list(map(int, input().split())) dp [0] * (n 1) dp[0] 1 for w in weights: for j in range(w, n 1): dp[j] dp[j - w] print(dp[n]) except EOFError: break这段代码非常短但有两个 Python 特有的坑需要注意。第一个坑是输入格式。题目可能把 m 个数字放在同一行也可能每个数字单独一行。上面代码假设同一行用空格分隔全部读完。但如果你用input()一行一行读遇到每个数字单独一行的情况就会出错。稳妥一点的做法是写一个生成器不断读取所有剩余输入再按空白字符切分这里不展开但强烈建议在写 UVa 题之前准备好一套稳定的多行输入模板。第二个坑是循环顺序。Python 里for j in range(w, n 1)天然就是正序完全没问题。如果你写代码时习惯性地想“倒序更安全”反过来写成了range(n, w - 1, -1)那就变成 0/1 背包了答案会错得很隐蔽。3.4 时间和空间复杂度结论状态数是 (O(mn))每个状态只做一次大数加法所以时间复杂度是 (O(mnL))其中 L 是结果数字的平均长度字符串加法本身需要 (O(L))。n≤100、m≤50、L 最多几十位这个复杂度在评测环境下非常轻松。空间复杂度是 (O(nL))因为要保存 n1 个字符串。n 只有 100就算每个字符串几十位内存也就是几 KB完全不紧张。即便把 n 放大到 10000这个一维字符串数组也仍然可行因为瓶颈更多是运行时间而不是内存。4. 问题排查与高分避坑把考场上的坑提前踩一遍4.1 组合还是排列循环顺序引发的“血案”我在前面反复强调内层循环正序很多人在本地手动测试几个小样例时觉得自己对了一交就 WA。看一个具体例子目标 n3纽扣尺寸为 1 和 2。正确答案是多少手工枚举{1,1,1}、{1,2}共 2 种。用正确的组合循环算初始化 dp[0] 1。处理尺寸 1dp[1] 1dp[2] 1dp[3] 1对应 {1}、{1,1}、{1,1,1}。处理尺寸 2dp[2] dp[0]得到 dp[2] 2对应 {1,1} 和 {2}dp[3] dp[1]此时 dp[1] 等于 1得到 dp[3] 2对应 {1,1,1} 和 {1,2}。最后 dp[3] 2正确。如果把内外层循环对调也就是先枚举容量 j再枚举纽扣种类 w代码会变成for (int j 1; j n; j) { for (int i 0; i m; i) { if (j w[i]) dp[j] dp[j - w[i]]; } }这样算出来的 dp[3] 等于 3因为 {1,2} 和 {2,1} 都被统计进去了多了一个顺序重复。为什么因为外层容量、内层物品时dp[j - w[i]] 会不断被当前容量 j 计算过程中新更新的其他物品方案覆盖形成了一条“可以从物品 A 跳到物品 B 再跳回 A”的路径结果把所有排列都计入。所以一个简单的自查方法如果题目说“不考虑顺序”那物品循环必须在外层如果题目明确说“不同顺序算不同方案”那容量循环在外层。这题属于前者。4.2 初始化、边界和输入终止条件边界情况是这类计数题最容易白给的地方。举几个具体场景第一n0 时输出什么答案是 1因为“什么都不选”本身是一个合法方案。很多同学初始化 dp[0]1 之后对这一行没有概念遇到 n0 直接不知道输出什么。记住计数型 DP 的通用约定空组合算一种。第二m0 且 n0 时输出什么答案是 0。没有纽扣凑不出任何正数。代码里如果 m0for 循环一次都不跑dp[n] 仍为初始值 0输出自然正确。但如果你把 dp[0] 初始化为 0那连 n0 的情况也会错所以初始化一定要用 dp[0]1。第三关于输入终止条件。有些题目用 n0 表示结束有些用 EOF。我前面代码里写的是“读到 n 且 n 不为 0”这是很多 UVa 题的风格。如果题面没有说明 n0 终止那就要改成普通的 while(cin n) 这种 EOF 读取方式。遇到多组输入题目先认真看清楚结尾条件不要想当然。4.3 重复尺寸到底要不要去重题目说纽扣“种类”不同但没有明确说同一尺寸会不会重复给出。假设输入里出现了两个相同的尺寸比如 2 和 2那么按“每个输入代表一类纽扣”来算选第一颗“尺寸2”和选第二颗“尺寸2”会被视为两种不同方案。但如果题目的本意是“尺寸为 2 的纽扣只有一种”那就应该先去重再 DP。我在实际处理时会先读一遍题面看它说的是“m 种不同尺寸”还是“m 个纽扣尺寸”。如果是后者相同数字就应该合并。UVa 12316 的常规解法我没有提前去重直接按输入的每一行作为一个种类处理也能通过因为在题目测试数据里同一组内出现完全相同的尺寸的概率很低而即使出现题目也倾向于把它们当作不同种类否则直接去重反而可能出错。这算是一个比较刁钻的边界如果你复现时遇到 WA可以试着在输入处加一个sortunique再跑一遍测试数据看看答案是否变化。多数情况下不会变但知道这个判断逻辑能帮你在排查时多一条路。4.4 大数运算的性能陷阱虽然这题 n 很小但大数加法也有性能问题需要留意。字符串加法每次分配新字符串如果内层循环次数多分配次数就多。我见过有人把 dp 数组定义成vectorvectorint每一位存大数的一位十进制数然后手工用循环做加法最后输出时拼接字符串。这种写法内存更大代码更啰嗦但性能其实差不多因为 n 实在太小。真正要小心的是不要在每次加法时都调用类似to_string(stoi(a) stoi(b))的函数。stoi会高位溢出结果完全错误。也不要使用long long中间变量去接大数结果再转字符串因为答案超过 long long 时直接就是错的。老老实实按位加进位处理好输出时不要在前面留多余的零。5. 题型扩展与个人刷题体会5.1 硬币问题的三个亲戚最少数量、组合数、排列数“用若干种硬币/纽扣/物品凑一个总额”这个模型几乎是动态规划里的常青树出题人能变出无数花样。我这里列三种最经典的变体刷题时可以对照着记。第一种是最少硬币数量。状态 dp[j] 表示凑出 j 的最小硬币数转移是 min。这类题对初始化要求是 dp[0]0其余为无穷大循环方向依然是内层正序完全背包。第二种是组合数也就是本题的模式。要求每个组合不区分顺序核心是物品循环在外层、容量循环在内层正序。第三种是排列数即顺序不同算不同方案。比如 LeetCode 377 这类题目解法是把容量循环放在外层物品循环放在内层。很多人在做这道题时突然想不明白其实就是把本题的循环对调了一下结果语义完全不同。还有一个更细的坑在组合数问题里如果把“每种硬币无限”改成“每种硬币最多用 k 次”那 dp 转移要从 0/1 背包变成多重背包计数复杂度也要提高。建议先把这四种基础情况整理成一个表刷题时对号入座。5.2 带数量上限、带模数的变体如果题目要求答案对某个大质数取模比如模 1e97那么大数计算就不用了每一步加法后取模即可。这种题的坑在于取模会改变“进位”逻辑所以不能再用字符串加法直接用long long做加法再取模。注意累加时两个 dp 值都要在模空间内否则可能溢出。如果需要限制每种纽扣最多使用次数就把完全背包变成多重背包。常见做法是把第 i 种物品按二进制拆分分成若干个 1 件、2 件、4 件……的 0/1 背包物品再进行 DP。对于计数问题更简单的方式是三重循环枚举第 i 种取多少件但复杂度会上升到 (O(mn^2))。n 小的时候没问题n 大的话必须优化。还有一种变体是输出具体方案或者字典序最小的方案这需要额外开一个 pre 数组记录转移来源。做这类题时先把握住基础模型的转移方向再一步步加条件就不会跑偏。5.3 一点个人刷题体会我自己做这种“陪伴感很强”的题目时最怕的是题目简单但读题不细。像 UVa 12316 这样的大数背包题其实算法层面没有任何高级技巧但把所有细节都做好需要一点点经验积累。我总结了一条固定套路拿到计数型背包题先确定三件事——初始化、循环顺序、结果精度。把这三件事写在草稿纸上再写代码基本上不会出大问题。之前在刷题群里见过一位同学状态转移写得完全正确但输出答案前加了一句“方案数可能很大请对 1000000007 取模”结果题目根本没让取模直接 WA 了两页。这提醒我做题前一定看清楚输出要求是输出完整大数还是输出模值。这题题目要求输出完整方案数所以我们的 addString 方案是最稳妥的。把这道题吃透之后再遇到“硬币找零计数”“任意背包方案数”“整数拆分”问题几乎可以秒杀。如果你正处在动态规划的入门阶段建议动手把这题的二维写法先写一遍再手动改成滚动数组。过程虽然有点重复但对理解完全背包的本质帮助很大。我自己当年也是这样一步步过来的现在看到这个题名反而会想起陪奶奶一起数纽扣的温馨画面。 
长河君 · 2026/10/10 4:54:51 · 阅读 1.2k UVa 12316 完全背包计数问题详解：状态设计、滚动数组与大数加法
第一次在题目列表里看到“Sewing Buttons with Grandma”UVa 12316时我以为是那种讲故事送温暖的题。读完题面发现这题翻译过来就是奶奶有一堆大小不一的纽扣每一种都有无限多颗她想凑出一个指定大小的总和问一共有几种凑法。没有感情戏没有场景描写剩下的全是背包问题。得祖母再慈祥该写状态转移还是得写。这题在很多算法爱好者看来是入门级别的完全背包计数题但它有一个很容易被人忽略的坑同样是“用无限物品凑总和”循环顺序写错答案就会从组合数变成排列数WA得毫无脾气。再加上答案可能特别大很多语言自带大数但C选手就得自己手写。这篇文章我会把这道题从读题、建模、状态设计、去重技巧、大数加法到踩坑经验全部过一遍适合正在刷动态规划基础题、尤其是背包专题的同学参考。1. 题目到底在做什么先把这个“缝扣子”问题翻译成数学题1.1 题面看着温馨条件其实很硬题目背景很简单奶奶要缝一件有很多扣眼的外套身边有一个装满纽扣的盒子。盒子里有若干种尺寸的纽扣每一种都不限数量。现在给定一个目标大小 n问用这些纽扣能凑出多少种不同的方案使得所选纽扣的尺寸总和恰好等于 n。比如目标大小是 5纽扣种类有两种尺寸 2 和尺寸 3。那么可以凑出的方案只有一种23。虽然你写代码时可能是先取 2 再取 3也可能先取 3 再取 2但“拿一颗 2 和一颗 3”这件事在物理世界里是同一个结果不能当成两种方案。这就是这道题和很多初学者的直觉最容易打架的地方。题目的输出是一串数字不是取模后的余数。也就是说方案数可能非常大甚至超出 64 位整数能表示的范围。这个细节直接决定了我们后面必须处理大数。很多人在状态转移都写对的情况下栽在这一步觉得“可能很大”就是“可能超过 int”结果用 long long 一交直接溢出输出一堆乱码。1.2 输入输出和数据范围题目是多组输入常见写法是读到文件末尾结束。每一组数据先给一个正整数 n表示需要凑出的目标大小接着给一个正整数 m表示纽扣的种类数然后给 m 个整数表示每种纽扣的尺寸。[ n \le 100,\quad m \le 50 ]这是题目中隐藏的关键信息。n 只有 100说明我们完全可以开一个长度为 n1 的 dp 数组不需要任何高级优化。m 也只有 50循环嵌套没有任何压力。真正的压力全在结果数字的长度上因为组合方案数是指数级别的哪怕 n 很小方案数也可能长到几十位甚至上百位。有些版本的题目会把 n 为 0 作为终止条件有些版本不会具体以你复现时的题面为准。我下面给出的代码按“读到 EOF遇到 n0 就结束”的常见风格处理如果没有这个约定删掉 break 分支即可。1.3 为什么直接判定为完全背包计数问题判断一个题是不是背包问题就看三个要素物品、容量、选择限制。这里的物品是纽扣种类容量是目标大小 n限制是每种纽扣可以取任意多颗。所以模型非常清晰完全背包但不是求最大价值而是求方案总数。这里最容易出现的一个误区是“这不就是组合数学里的正整数拆分吗能不能用生成函数、母函数去解”理论上可以生成函数的系数就是答案但写起来比动态规划复杂而且在大数场景下没有任何优势。对 OJ 来说动态规划就是最标准、最稳妥、最好写的解法。还有一点值得提醒有些同学第一眼看到“无限取”就想到高中数学里的隔板法、整数拆分公式但库里尺寸不是从 1 到 n 的连续整数而是给定的任意正整数序列。比如可能只有尺寸 3 和尺寸 5没有 1 和 2。这种情况下整数拆分公式完全不适用必须老老实实用背包。2. 解题思路拆解从暴力枚举到动态规划2.1 暴力枚举为什么活不过两秒最朴素的想法是枚举每种纽扣取多少颗。设第 i 种纽扣取了 (c_i) 颗那么要满足[ \sum_{i1}^{m} c_i \times w_i n ]这个枚举的规模有多大最坏情况下每一种纽扣的取值都有 (O(n / w_i)) 种可能全部组合起来是乘积级别。n100m50 时即使每种尺寸都比较大暴力组合也会轻松爆炸。就算剪枝枚举过程中还涉及“判断是否重复”的问题因为纽扣组合不区分顺序枚举生成的有序组合还要再做一次去重复杂度根本不可接受。所以这题必须用动态规划。动态规划的好处是它把“用前 i 种纽扣凑某个总和”这件事做成状态通过递推避免重复计算同时天然规避了顺序问题。2.2 状态定义让“前 i 种”成为核心维度定义状态[ dp[i][j] 前 i 种纽扣凑出总大小 j 的方案数 ]其中 i 从 0 到 mj 从 0 到 n。这里“前 i 种”是严格有序的我们先把所有纽扣种类从左到右排好队考虑前 1 种、前 2 种……这样在计算时方案集合被一张“种类先后”的标签隔离永远不会把同一种组合通过不同顺序重复计入。初始化也很直观前 0 种纽扣凑出总大小 0 的方案数是 1也就是什么都不取前 0 种纽扣凑出任何大于 0 的总大小都是 0因为没有任何纽扣可用。[ dp[0][0] 1 ][ dp[0][j] 0 \quad (j 0) ]2.3 转移方程选 0 个和至少选 1 个有了状态怎么从前面的状态推到当前状态对第 i 种纽扣尺寸为 w我们有两种情况的叠加。第一完全不使用第 i 种纽扣。那么方案就是从“前 i-1 种”凑出 j[ dp[i][j] dp[i-1][j] ]第二至少使用 1 颗第 i 种纽扣。可以先拿掉一颗尺寸为 w 的纽扣剩下的 j-w 仍然允许继续使用第 i 种因为数量无限[ dp[i][j] dp[i][j-w] \quad (j \ge w) ]这里需要仔细体会为什么是 (dp[i][j-w]) 而不是 (dp[i-1][j-w])因为当我们“已经决定至少放一颗第 i 种纽扣”时剩余的 j-w 还可以再放第 i 种纽扣这是一种递归式的定义。如果写成 (dp[i-1][j-w])就只能放一颗第 i 种纽扣第二颗、第三颗都放不了那就退化成 0/1 背包了。完整的转移就是[ dp[i][j] dp[i-1][j] (j \ge w \text{ 时 } dp[i][j-w]) ]这个写法我在刚开始学的时候总觉得有点绕后来用一个生活例子理解你在自助餐厅拿菜面前有“前 i 道菜”的取餐区。要么这一轮完全跳过第 i 道菜那么方案数继承“前 i-1 道菜”的情况要么你至少夹一筷子第 i 道菜夹完之后你还可以接着夹这道菜于是问题回到“前 i 道菜”里凑 j-w 的剩余量。这样就既允许无限取又因为没有给第 i 道菜设置“排列顺序”不会把同一道菜的不同夹取顺序重复计数。2.4 一维压缩从二维表到滚动数组观察转移式(dp[i][j]) 只依赖 (dp[i-1][j]) 和 (dp[i][j-w])。前者是上一行的旧值后者是本行前面位置刚算出来的新值。所以我们可以只用一个一维数组按顺序覆盖更新。[ dp[j] dp[j] dp[j-w] \quad (j \text{ 从小到大遍历}) ]这里的内层循环顺序非常关键必须从小到大遍历 j。因为 (dp[j-w]) 在 (j) 之前已经被更新过它代表的正是同一轮内“已经使用了第 i 种纽扣”的方案数这正好对应完全背包“允许无限使用”的特性。如果改成从大到小遍历(dp[j-w]) 还是上一轮的旧值那就变成 0/1 背包每种纽扣最多用一次。这个“正序还是倒序”的细节是背包问题里的老演员了但每次考试还是有人错。我的习惯是记一句话完全背包正序0/1 背包倒序。做题前先想清楚这题是无限取还是一次取再决定方向。3. 代码实现与关键细节大数、初始化、循环顺序3.1 大数加法自己动手不用库先回答一个问题这题的方案数到底能有多大n100、m50、所有纽扣尺寸都是 1 时答案是 (2^{99}) 级别的天文数字大约 30 位十进制数。如果尺寸更小、种类更多还能更大。long long 只能存到 (9.22 \times 10^{18})连零头都不够所以必须用大数。C 在 ACM 环境下最稳妥的做法是自己写一个字符串加法。加法逻辑不难按位从低位到高位加处理进位。写一次通用函数后面所有类似“计数型背包”的题都能直接用。这里我给出一个可靠实现版本string addString(const string a, const string b) { string res; int i (int)a.size() - 1; int j (int)b.size() - 1; int carry 0; while (i 0 || j 0 || carry) { int sum carry; if (i 0) sum a[i--] - 0; if (j 0) sum b[j--] - 0; carry sum / 10; res.push_back(char(0 sum % 10)); } reverse(res.begin(), res.end()); return res; }这个函数每次生成一个新的字符串虽然会有额外开销但在 n≤100 的场景下完全足够。如果你担心多次分配字符串导致超时也可以用固定长度的 char 数组配合手写进位但一般情况下没必要。3.2 C 参考实现下面给出一个可以直接 AC 的完整实现。为了节省空间dp 数组直接开一维并且用 string 类型存储大数。首先初始化 dp 数组为全 0再把 dp[0] 设置为 1表示凑出大小为 0 的方案有一种。然后外层循环枚举纽扣种类内层循环用正序更新 dp。最终 dp[n] 就是答案。#include bits/stdc.h using namespace std; string addString(const string a, const string b) { string res; int i (int)a.size() - 1; int j (int)b.size() - 1; int carry 0; while (i 0 || j 0 || carry) { int sum carry; if (i 0) sum a[i--] - 0; if (j 0) sum b[j--] - 0; carry sum / 10; res.push_back(char(0 sum % 10)); } reverse(res.begin(), res.end()); return res; } int main() { int n; while (cin n n) { int m; cin m; vectorint w(m); for (int i 0; i m; i) { cin w[i]; } vectorstring dp(n 1, 0); dp[0] 1; for (int i 0; i m; i) { for (int j w[i]; j n; j) { dp[j] addString(dp[j], dp[j - w[i]]); } } cout dp[n] \n; } return 0; }这段代码里最需要注意的就是for (int j w[i]; j n; j)内层从 w[i] 开始从小到大走到 n。很多人在写完全背包求方案数时习惯用二维数组然后手动写三重循环枚举第 i 种取 k 个那样也能过但代码更长也更难查错。一维写法干净利落前提是理解清楚“正序更新”的含义。3.3 Python 对照享受语言红利但也别掉坑如果你平时刷题用 Python那大数问题直接消失因为 Python 的整数没有位数限制。同样的逻辑翻译成 Pythonwhile True: try: n int(input()) if n 0: break m int(input()) weights list(map(int, input().split())) dp [0] * (n 1) dp[0] 1 for w in weights: for j in range(w, n 1): dp[j] dp[j - w] print(dp[n]) except EOFError: break这段代码非常短但有两个 Python 特有的坑需要注意。第一个坑是输入格式。题目可能把 m 个数字放在同一行也可能每个数字单独一行。上面代码假设同一行用空格分隔全部读完。但如果你用input()一行一行读遇到每个数字单独一行的情况就会出错。稳妥一点的做法是写一个生成器不断读取所有剩余输入再按空白字符切分这里不展开但强烈建议在写 UVa 题之前准备好一套稳定的多行输入模板。第二个坑是循环顺序。Python 里for j in range(w, n 1)天然就是正序完全没问题。如果你写代码时习惯性地想“倒序更安全”反过来写成了range(n, w - 1, -1)那就变成 0/1 背包了答案会错得很隐蔽。3.4 时间和空间复杂度结论状态数是 (O(mn))每个状态只做一次大数加法所以时间复杂度是 (O(mnL))其中 L 是结果数字的平均长度字符串加法本身需要 (O(L))。n≤100、m≤50、L 最多几十位这个复杂度在评测环境下非常轻松。空间复杂度是 (O(nL))因为要保存 n1 个字符串。n 只有 100就算每个字符串几十位内存也就是几 KB完全不紧张。即便把 n 放大到 10000这个一维字符串数组也仍然可行因为瓶颈更多是运行时间而不是内存。4. 问题排查与高分避坑把考场上的坑提前踩一遍4.1 组合还是排列循环顺序引发的“血案”我在前面反复强调内层循环正序很多人在本地手动测试几个小样例时觉得自己对了一交就 WA。看一个具体例子目标 n3纽扣尺寸为 1 和 2。正确答案是多少手工枚举{1,1,1}、{1,2}共 2 种。用正确的组合循环算初始化 dp[0] 1。处理尺寸 1dp[1] 1dp[2] 1dp[3] 1对应 {1}、{1,1}、{1,1,1}。处理尺寸 2dp[2] dp[0]得到 dp[2] 2对应 {1,1} 和 {2}dp[3] dp[1]此时 dp[1] 等于 1得到 dp[3] 2对应 {1,1,1} 和 {1,2}。最后 dp[3] 2正确。如果把内外层循环对调也就是先枚举容量 j再枚举纽扣种类 w代码会变成for (int j 1; j n; j) { for (int i 0; i m; i) { if (j w[i]) dp[j] dp[j - w[i]]; } }这样算出来的 dp[3] 等于 3因为 {1,2} 和 {2,1} 都被统计进去了多了一个顺序重复。为什么因为外层容量、内层物品时dp[j - w[i]] 会不断被当前容量 j 计算过程中新更新的其他物品方案覆盖形成了一条“可以从物品 A 跳到物品 B 再跳回 A”的路径结果把所有排列都计入。所以一个简单的自查方法如果题目说“不考虑顺序”那物品循环必须在外层如果题目明确说“不同顺序算不同方案”那容量循环在外层。这题属于前者。4.2 初始化、边界和输入终止条件边界情况是这类计数题最容易白给的地方。举几个具体场景第一n0 时输出什么答案是 1因为“什么都不选”本身是一个合法方案。很多同学初始化 dp[0]1 之后对这一行没有概念遇到 n0 直接不知道输出什么。记住计数型 DP 的通用约定空组合算一种。第二m0 且 n0 时输出什么答案是 0。没有纽扣凑不出任何正数。代码里如果 m0for 循环一次都不跑dp[n] 仍为初始值 0输出自然正确。但如果你把 dp[0] 初始化为 0那连 n0 的情况也会错所以初始化一定要用 dp[0]1。第三关于输入终止条件。有些题目用 n0 表示结束有些用 EOF。我前面代码里写的是“读到 n 且 n 不为 0”这是很多 UVa 题的风格。如果题面没有说明 n0 终止那就要改成普通的 while(cin n) 这种 EOF 读取方式。遇到多组输入题目先认真看清楚结尾条件不要想当然。4.3 重复尺寸到底要不要去重题目说纽扣“种类”不同但没有明确说同一尺寸会不会重复给出。假设输入里出现了两个相同的尺寸比如 2 和 2那么按“每个输入代表一类纽扣”来算选第一颗“尺寸2”和选第二颗“尺寸2”会被视为两种不同方案。但如果题目的本意是“尺寸为 2 的纽扣只有一种”那就应该先去重再 DP。我在实际处理时会先读一遍题面看它说的是“m 种不同尺寸”还是“m 个纽扣尺寸”。如果是后者相同数字就应该合并。UVa 12316 的常规解法我没有提前去重直接按输入的每一行作为一个种类处理也能通过因为在题目测试数据里同一组内出现完全相同的尺寸的概率很低而即使出现题目也倾向于把它们当作不同种类否则直接去重反而可能出错。这算是一个比较刁钻的边界如果你复现时遇到 WA可以试着在输入处加一个sortunique再跑一遍测试数据看看答案是否变化。多数情况下不会变但知道这个判断逻辑能帮你在排查时多一条路。4.4 大数运算的性能陷阱虽然这题 n 很小但大数加法也有性能问题需要留意。字符串加法每次分配新字符串如果内层循环次数多分配次数就多。我见过有人把 dp 数组定义成vectorvectorint每一位存大数的一位十进制数然后手工用循环做加法最后输出时拼接字符串。这种写法内存更大代码更啰嗦但性能其实差不多因为 n 实在太小。真正要小心的是不要在每次加法时都调用类似to_string(stoi(a) stoi(b))的函数。stoi会高位溢出结果完全错误。也不要使用long long中间变量去接大数结果再转字符串因为答案超过 long long 时直接就是错的。老老实实按位加进位处理好输出时不要在前面留多余的零。5. 题型扩展与个人刷题体会5.1 硬币问题的三个亲戚最少数量、组合数、排列数“用若干种硬币/纽扣/物品凑一个总额”这个模型几乎是动态规划里的常青树出题人能变出无数花样。我这里列三种最经典的变体刷题时可以对照着记。第一种是最少硬币数量。状态 dp[j] 表示凑出 j 的最小硬币数转移是 min。这类题对初始化要求是 dp[0]0其余为无穷大循环方向依然是内层正序完全背包。第二种是组合数也就是本题的模式。要求每个组合不区分顺序核心是物品循环在外层、容量循环在内层正序。第三种是排列数即顺序不同算不同方案。比如 LeetCode 377 这类题目解法是把容量循环放在外层物品循环放在内层。很多人在做这道题时突然想不明白其实就是把本题的循环对调了一下结果语义完全不同。还有一个更细的坑在组合数问题里如果把“每种硬币无限”改成“每种硬币最多用 k 次”那 dp 转移要从 0/1 背包变成多重背包计数复杂度也要提高。建议先把这四种基础情况整理成一个表刷题时对号入座。5.2 带数量上限、带模数的变体如果题目要求答案对某个大质数取模比如模 1e97那么大数计算就不用了每一步加法后取模即可。这种题的坑在于取模会改变“进位”逻辑所以不能再用字符串加法直接用long long做加法再取模。注意累加时两个 dp 值都要在模空间内否则可能溢出。如果需要限制每种纽扣最多使用次数就把完全背包变成多重背包。常见做法是把第 i 种物品按二进制拆分分成若干个 1 件、2 件、4 件……的 0/1 背包物品再进行 DP。对于计数问题更简单的方式是三重循环枚举第 i 种取多少件但复杂度会上升到 (O(mn^2))。n 小的时候没问题n 大的话必须优化。还有一种变体是输出具体方案或者字典序最小的方案这需要额外开一个 pre 数组记录转移来源。做这类题时先把握住基础模型的转移方向再一步步加条件就不会跑偏。5.3 一点个人刷题体会我自己做这种“陪伴感很强”的题目时最怕的是题目简单但读题不细。像 UVa 12316 这样的大数背包题其实算法层面没有任何高级技巧但把所有细节都做好需要一点点经验积累。我总结了一条固定套路拿到计数型背包题先确定三件事——初始化、循环顺序、结果精度。把这三件事写在草稿纸上再写代码基本上不会出大问题。之前在刷题群里见过一位同学状态转移写得完全正确但输出答案前加了一句“方案数可能很大请对 1000000007 取模”结果题目根本没让取模直接 WA 了两页。这提醒我做题前一定看清楚输出要求是输出完整大数还是输出模值。这题题目要求输出完整方案数所以我们的 addString 方案是最稳妥的。把这道题吃透之后再遇到“硬币找零计数”“任意背包方案数”“整数拆分”问题几乎可以秒杀。如果你正处在动态规划的入门阶段建议动手把这题的二维写法先写一遍再手动改成滚动数组。过程虽然有点重复但对理解完全背包的本质帮助很大。我自己当年也是这样一步步过来的现在看到这个题名反而会想起陪奶奶一起数纽扣的温馨画面。