1. 项目概述从整数划分到完全背包的思维跃迁在算法学习与竞赛准备中我们常常会遇到一类经典问题整数划分。题目描述通常简洁而深刻——给定一个正整数n要求计算将n表示为若干个正整数之和的所有不同方案数。例如对于n 5其划分方式包括5、41、32、311、221、2111、11111共计7种。初看之下这似乎是一个纯粹的数学组合问题或者可以用深度优先搜索DFS来暴力枚举。然而当n的规模达到几百甚至上千时搜索的指数级时间复杂度将使其变得不可行。这时动态规划DP便成为我们手中的利器。但动态规划的思路不止一种。最直观的想法可能是将其视为一个“计数DP”问题定义f[i][j]为使用前i个正整数1, 2, ..., i构成总和为j的方案数。这个思路本身没有问题但其状态转移方程考虑是否使用数字i与经典的背包问题模型有着惊人的相似性。如果我们把要划分的整数n看作背包的容量把数字1, 2, ..., n看作无限多件、体积和价值均为其自身数值的物品那么“求恰好装满容量为n的背包的方案数”这个问题就与“整数划分”完美等价了。这正是“完全背包求方案数”模板的核心思想。这个思维转换的价值巨大。它意味着我们无需为整数划分单独记忆一套复杂的递推公式而是可以直接套用经过千锤百炼的完全背包模型及其优化技巧。对于正在刷题尤其是系统学习Acwing算法基础课的朋友来说掌握这个模板就相当于打通了“计数类DP”和“背包DP”之间的任督二脉。无论是应对算法笔试面试还是加深对动态规划本质的理解这都是一块不可或缺的拼图。本文将彻底拆解这个模板从为什么能这样转换到状态定义、转移方程、初始化、空间优化再到代码实现和易错点分析让你不仅会套模板更能理解其背后的每一处精妙设计。2. 核心思路解析为什么整数划分是完全背包问题理解这个问题的关键在于建立正确的数学模型。我们一步步来拆解。2.1 问题重述与类比建立整数划分问题给定正整数n求其拆分成若干个正整数之和的方案数。顺序不同的序列视为同一种方案例如23和32是同一种划分。完全背包问题有N种物品和一个容量为V的背包。每种物品都有无限件可用第i种物品的体积是v_i价值是w_i。求解将哪些物品装入背包可使这些物品的总体积不超过背包容量且总价值最大或求方案数等其他目标。现在我们建立类比背包容量V对应我们要划分的整数n。物品正整数1, 2, 3, ..., n。我们可以使用的“数字”就是这些物品。物品体积v_i数字i本身的大小。因为我们要用数字去“填充”总和n数字的大小就是它占据的“空间”。物品价值w_i在这个问题中我们只关心方案数不关心最大价值所以价值的概念暂时可以忽略或者认为价值也是i但这不影响方案数计算。物品数量每种数字物品可以无限次使用。因为一个划分里可以包含多个相同的数字例如多个1。目标转换从“求恰好装满容量为n的背包的方案数”变成了“求用数字1到n每种无限个恰好组成总和n的方案数”。这二者在数学描述上完全一致。注意这里有一个关键点为什么物品是1到n而不是无限种因为要组成总和n任何大于n的数字本身就无法使用一件物品的体积就超过了背包容量所以有效的“物品”集合就是1, 2, ..., n。2.2 状态定义与转移方程推导既然我们将其归约为完全背包模型就可以直接套用完全背包求方案数的DP思路。我们定义动态规划数组f[i][j]含义考虑前i种物品即数字1到i恰好装满容量为j的背包即用这些数字凑出总和j的所有方案数。最终答案f[n][n]即考虑数字1到n凑出总和n的方案数。接下来推导状态转移方程。对于当前状态f[i][j]我们考虑第i种物品即数字i的使用情况不使用数字i那么方案数就等于只使用前i-1种数字凑出j的方案数即f[i-1][j]。使用至少一个数字i如果我们决定使用数字i那么我们先放一个i进去。此时背包剩余容量为j - i。注意因为物品i有无限个在使用了这一个i之后我们仍然可以继续使用前i种物品包括i本身去填满剩下的容量j-i。因此这部分方案数就是f[i][j-i]。为什么是f[i][j-i]而不是f[i-1][j-i]这是完全背包与01背包在状态转移上的核心区别。在01背包中每种物品只能用一次所以使用了物品i后只能从前i-1种物品里继续选对应f[i-1][j-v_i]。而在完全背包中物品无限使用了物品i后背包容量减少但依然可以继续选择物品i因此状态是转移到f[i][j-v_i]即同一行i不变的前面某一列。将两种情况合并我们得到完全背包求方案数的经典状态转移方程f[i][j] f[i-1][j] f[i][j-i]边界条件初始化f[0][0] 1考虑前0种物品即没有任何数字凑出总和0的方案数为1“什么都不选”本身算一种方案。这是所有方案数DP的常见起点。对于其他位置f[0][j] (j0) 0没有数字可用却要凑出正数和这是不可能的方案数为0。2.3 与另一种DP思路的对比你可能也见过另一种直接的整数划分DP定义f[i][j]表示总和为i恰好被划分成j个数的方案数。这种定义需要二维状态且最终答案需要对j从1到n求和其转移方程也较为复杂f[i][j] f[i-1][j-1] f[i-j][j]。相比之下完全背包模型具有显著优势思维经济无需创造新的DP模型直接复用已经深入理解的完全背包框架降低学习成本。状态定义直观“使用前i种物品凑容量j”比“总和i分成j个数”在背包语境下更自然。易于优化完全背包的空间优化滚动数组、一维数组是标准套路直接套用即可。而另一种定义的空间优化则不那么直观。扩展性强此模板稍加修改就能解决“整数划分中每个数不超过某个值”、“使用特定数字集合进行划分”等变体问题。因此将整数划分视为完全背包求方案数是一个化繁为简、高效优雅的解决方案。3. 代码实现与逐行精讲理论清晰后我们来看代码实现。这里将给出从最朴素的二维DP到极致优化的一维DP的完整演进过程并解释每一行代码的意义。3.1 朴素二维DP实现这是最直接对应状态转移方程f[i][j] f[i-1][j] f[i][j-i]的写法有助于我们理解本质。#include iostream using namespace std; const int N 1010, MOD 1e9 7; // 假设n最大为1000结果需要对1e97取模 int f[N][N]; // f[i][j] 含义如前所述 int main() { int n; cin n; // 初始化 f[0][0] 1; // 边界条件 // 其他f[0][j] (j0) 在全局数组中默认为0符合定义 // 动态规划过程 for (int i 1; i n; i) { // 枚举物品数字1到n for (int j 0; j n; j) { // 枚举背包容量总和0到n // 不选数字i的情况 f[i][j] f[i-1][j]; // 如果容量j足够放下至少一个数字i则加上选的情况 if (j i) { f[i][j] (f[i][j] f[i][j - i]) % MOD; } } } cout f[n][n] endl; return 0; }逐行精讲const int N 1010根据题目数据范围设定数组大小通常留有余量。MOD结果往往很大要求取模这是算法题常见要求。f[0][0] 1这是整个DP的“种子”。没有数字时凑出0只有一种方案空集。外层循环for (int i 1; i n; i)i代表当前考虑的物品范围前i种数字。从1开始因为数字从1开始。内层循环for (int j 0; j n; j)j代表当前要凑的总和背包容量。必须从0开始因为f[i][0]有意义用前i种数字凑0方案数为1即什么都不选。f[i][j] f[i-1][j]先继承“不选数字i”的方案数。if (j i)只有当当前容量j大于等于数字i的体积时才有可能选择i。f[i][j] (f[i][j] f[i][j - i]) % MOD这是核心加上“选择至少一个数字i”的方案数。注意是f[i][j-i]体现了完全背包的“同一行”转移。同时进行取模运算。这个版本的时间复杂度和空间复杂度都是O(n^2)。对于n1000是可行的但如果n更大空间可能成为瓶颈。3.2 空间优化滚动数组两行数组观察状态转移方程f[i][j] f[i-1][j] f[i][j-i]我们发现计算第i行时只依赖于第i-1行和本行前面的列。因此我们不需要保存整个n x n的矩阵只需要保存两行当前行和上一行即可。#include iostream using namespace std; const int N 1010, MOD 1e9 7; int f[2][N]; // 只开两行用 i % 2 来滚动 int main() { int n; cin n; f[0][0] 1; // 初始化对应 i0 行 for (int i 1; i n; i) { int cur i % 2, prev (i - 1) % 2; // cur:当前行prev:上一行 for (int j 0; j n; j) { // 先继承上一行不选i f[cur][j] f[prev][j]; // 如果可选i则加上本行前面的状态 if (j i) { f[cur][j] (f[cur][j] f[cur][j - i]) % MOD; // 注意这里是 f[cur][j-i] } } } cout f[n % 2][n] endl; // 输出最终结果所在的行 return 0; }优化点数组大小从f[N][N]变为f[2][N]空间复杂度从O(n^2)降为O(n)。通过cur和prev两个变量巧妙地切换当前行和上一行。注意第12行f[cur][j] f[prev][j]实现了“不选i”的转移。第15行f[cur][j] (f[cur][j] f[cur][j - i]) % MOD这里的f[cur][j-i]可能在本轮循环中已经被更新过了因为j-ij这恰恰是完全背包所允许和需要的与一维优化原理相通。3.3 终极优化一维数组这是完全背包问题最经典也最简洁的空间优化。我们直接使用一个一维数组f[j]其含义是恰好凑成总和j的方案数。在迭代过程中我们隐式地处理了“物品维度”。#include iostream using namespace std; const int N 1010, MOD 1e9 7; int f[N]; // f[j] 表示恰好凑成总和j的方案数 int main() { int n; cin n; f[0] 1; // 初始化凑成0的方案数为1 for (int i 1; i n; i) { // 枚举物品i数字1到n for (int j i; j n; j) { // 枚举容量j从i开始 f[j] (f[j] f[j - i]) % MOD; } } cout f[n] endl; return 0; }这段代码极其简洁但内涵丰富需要仔细理解f[0] 1同样是“种子”凑0的方案数为1。外层循环for (int i 1; i n; i)这层循环按顺序考虑每个数字物品。你可以理解为我们正在一件一件地“解锁”这些数字并更新我们的方案数数组。内层循环for (int j i; j n; j)为什么j从i开始因为如果j i当前数字i的体积已经超过当前要凑的总和j根本不可能被使用所以f[j]保持不变即只包含不使用数字i的方案而这些方案在上一轮i-1循环结束后已经存储在f[j]中了。因此直接从j i开始遍历。为什么j要从小到大遍历这是完全背包一维优化的精髓也是与01背包一维优化j从大到小遍历的核心区别。当我们计算f[j]时我们需要用到f[j - i]。如果j从小到大遍历那么在计算f[j]时f[j - i]已经在本轮外层循环 (i相同) 中被更新过了。f[j - i]此时代表的是“考虑过数字i后凑成总和j-i的方案数”。这意味着在凑j-i的方案里可能已经包含了若干个数字i。那么f[j] f[j] f[j-i]就等价于在之前方案不含i或含更小的i的基础上加上那些已经包含了一些i的方案里再塞入一个i所能形成的新方案。这正好实现了“物品i可以取无限件”的逻辑。反之如果j从大到小遍历像01背包那样那么计算f[j]时用到的f[j-i]是上一轮外层循环即考虑数字i-1时的结果这意味着每个数字i最多被使用一次这就退化成了01背包。一维数组f[j]的语义演变 在循环开始时f[j]保存的是“只考虑前i-1种数字时凑成总和j的方案数”。 经过内层循环对j的遍历后f[j]被更新为“考虑前i种数字时凑成总和j的方案数”。 当外层循环结束时i nf[n]自然就是考虑所有数字1到n时的答案。实操心得一维优化代码虽短但理解其“为何从小到大遍历”是掌握完全背包模板的关键。一个简单的记忆口诀完全背包一维化内循环容量要正序从小到大01背包一维化内循环容量要逆序从大到小。写代码时多想想这个区别能避免很多错误。4. 模板的变体与扩展应用掌握了基础模板我们来看看它能解决哪些变体问题这能极大地提升我们举一反三的能力。4.1 变体一划分成若干个不同正整数的方案数如果要求划分出的正整数必须互不相同那么问题就变成了有n种物品数字1到n每种物品最多选一次因为不能重复求恰好装满容量为n的背包的方案数。这实际上是一个01背包求方案数问题。状态转移方程二维f[i][j] f[i-1][j] f[i-1][j-i]一维优化内层循环j需要从大到小遍历。f[0] 1; for (int i 1; i n; i) { for (int j n; j i; j--) { // 逆序 f[j] (f[j] f[j - i]) % MOD; } } cout f[n] endl;只需要将内循环的顺序从j i; j n改为j n; j i模板就瞬间从“完全背包”切换到了“01背包”。这再次体现了背包模型强大的通用性。4.2 变体二划分成若干个奇数的方案数如果要求划分出的所有数都是奇数。我们只需要修改“物品集合”。此时有效的数字是1, 3, 5, ...,最大不超过n的奇数。我们依然可以无限次使用每个奇数。代码调整外层循环遍历奇数即可。f[0] 1; for (int i 1; i n; i 2) { // i从1开始每次加2只遍历奇数 for (int j i; j n; j) { f[j] (f[j] f[j - i]) % MOD; } } cout f[n] endl;甚至这个问题有更巧妙的数学转化一个正整数划分成若干个奇数的方案数等于其划分成若干个正整数不限奇偶的方案数。但用修改物品集合的DP方法思维负担更小更通用。4.3 变体三求划分方案的具体内容输出所有划分有时题目不仅要求方案数还要求输出所有具体的划分方式。此时DP求方案数的方法依然可以作为基础用于快速计算方案总数避免无效搜索但具体输出需要结合深度优先搜索DFS。思路是先用DP计算出总方案数如果只需要判断是否存在或数量不大也可以不用DP然后用DFS进行构造。DFS时为了避免重复如23和32我们强制规定划分中的数字以非递增顺序排列即后一个数不大于前一个数。#include iostream #include vector using namespace std; const int N 20; // 假设n较小方便输出 int n; vectorint path; void dfs(int remaining, int start) { // remaining: 剩余需要划分的数值 // start: 当前可以选择的数字的最小值保证非递增 if (remaining 0) { // 找到一种划分输出 for (int i 0; i path.size(); i) { cout path[i]; if (i ! path.size() - 1) cout ; } cout endl; return; } // 从start开始枚举当前层要选的数字 for (int i start; i 1; i--) { // 从大到小枚举保证非递增 if (remaining i) { path.push_back(i); dfs(remaining - i, i); // 下一层最多从i开始选 path.pop_back(); // 回溯 } } } int main() { cin n; dfs(n, n); // 初始剩余n最大可选数字为n return 0; }这个DFS函数能按字典序逆序因为从大到小枚举输出所有划分。DP与DFS结合是解决“求具体方案”类问题的常见套路。5. 常见问题与调试技巧实录在实际编写和调试这类DP代码时会遇到一些典型问题。这里记录几个我踩过的坑和解决方法。5.1 问题一初始化错误导致结果全为0或过大症状程序运行后输出0或者输出一个巨大的、不合理的数可能是负数因为取模前溢出了。根因几乎都是f[0]初始化错误。如果输出0检查是否忘记了f[0] 1。没有这个“种子”任何方案都无法递推出来。如果输出巨大负数检查是否在累加时没有及时取模导致int类型溢出。确保每次加法后都% MOD。调试技巧对于DP问题总是先打印出小规模n比如1, 2, 3, 4的整个f数组一维或二维手动验算一下。对于n4方案数应为54, 31, 22, 211, 1111。如果你的f数组最终f[4]不是5就从f[0],f[1]开始一步步核对。5.2 问题二一维优化时内循环顺序写反症状当n较小时结果可能对但n稍大结果就明显错误且往往比正确答案小。根因混淆了完全背包和01背包的一维优化顺序。完全背包求方案数内循环j从小到大。01背包求方案数内循环j从大到小。如果你把完全背包写成了从大到小那么每个数字i实际上只被用了一次你计算的是“数字不重复”的划分方案数。记忆口诀完全正序01逆序。写代码前在心里默念一遍。5.3 问题三模运算处理不当症状结果错误或者在一些在线判题系统上得到“答案错误”但自己测小数据又好像对。根因取模运算的时机或方式不对。累加前取模f[j] f[j] f[j-i];然后再f[j] % MOD;这样写在中间累加时f[j]可能已经溢出。应该在加法运算时就取模f[j] (f[j] f[j-i]) % MOD;。负数取模在C中(a - b) % MOD如果a-b为负数结果会是负数。如果需要得到非负余数应该写成(a - b MOD) % MOD。不过在纯加法的方案数DP中通常不会遇到减法。初始化也要取模吗f[0]11本身就在模数范围内不需要。但如果初始化其他值为很大的数可能需要。5.4 问题四数组大小开不够症状程序在运行时发生段错误Segmentation Fault或访问越界。根因f数组长度N小于n1。注意我们的循环是j n因此数组下标会访问到f[n]所以数组大小至少要是n1。通常习惯开N n_max 10留出余量。5.5 性能分析与优化点对于本题的完全背包模板时间复杂度是O(n^2)空间复杂度优化后是O(n)。当n在5000以内时O(n^2)的算法约2500万次操作在现代计算机上可以在1秒内完成。如果n达到10^4或更大可能需要考虑更优的算法例如利用生成函数或五边形数定理其复杂度可达O(n sqrt(n))。但那些属于数论范畴在一般的算法竞赛或面试中掌握这个O(n^2)的DP模板已经足够应对绝大多数情况。一个小的常数优化在一维DP代码中内层循环for (int j i; j n; j)我们让j从i开始这避免了对j i的无谓判断和赋值操作。虽然编译器优化可能也会做类似的事情但自己写出来代码更清晰也体现了对算法的理解。6. 从模板到精通理解本质与举一反三经过上面的详细拆解我们已经将“整数划分”这个题目通过完全背包的视角转化为了一个清晰可套用的模板。但学习算法死记硬背模板是远远不够的更重要的是理解其本质并能够灵活运用。本质理解这个模板的本质是动态规划中的“计数DP”其核心在于状态定义和不重不漏的转移。“不重”我们通过“考虑前i种物品”这个维度有序地引入物品避免了像12和21这样的顺序重复。“不漏”状态转移方程f[i][j] f[i-1][j] f[i][j-i]覆盖了“不使用i”和“使用至少一个i”这两种所有可能的情况。举一反三的训练建议自行推导合上电脑拿出一张纸从零开始推导状态定义和转移方程。问自己为什么是f[i][j-i]而不是f[i-1][j-i]一维优化时为什么j要从小到大修改条件尝试解决前面提到的几个变体不同整数、奇数。再想想如果要求划分成的数字个数恰好为k个该如何修改状态定义提示增加一维状态f[i][j][k]或者用两个平行的一维数组输出路径如果要求输出字典序最小的划分方案该如何在DP的基础上记录路径并回溯联系其他问题思考“硬币找零问题”有无限枚不同面值的硬币求凑成某金额的方案数和本题的异同。你会发现它就是完全背包求方案数的直接应用只是“物品体积”变成了硬币面值。最后这个模板的价值不仅在于解决一道题。它提供了一种强大的思维工具将复杂的组合计数问题转化为具有“选择”和“容量”概念的背包模型。当你以后遇到类似“在若干限制条件下求达成某个目标的方案数”的问题时不妨想想能不能定义“物品”和“背包容量”如果能那么你就可能将一个陌生问题拉回到你熟悉的DP轨道上来。这或许就是学习和练习算法模板的最高意义。