1. 从“整数划分”到“完全背包”一个经典问题的本质洞察在算法学习与竞赛中“整数划分”是一个绕不开的经典问题。它的描述简单到极致给定一个正整数n要求计算出n可以表示成多少个正整数之和的不同方式。例如n 5那么5 5、5 41、5 32、5 311、5 221、5 2111、5 11111一共是7种划分方式。这个问题看似是一个纯粹的数学组合问题但当你深入思考其背后的计算逻辑时会发现它与动态规划中另一个鼎鼎大名的模型——“完全背包”问题有着惊人的内在一致性。很多初学者在初次接触时可能会尝试用递归或搜索去枚举所有组合但一旦n的规模稍大比如超过30这类方法的时间开销就会变得难以接受。这时理解并掌握“完全背包”的视角就成了解开这道题、乃至一类题目的万能钥匙。为什么说整数划分问题可以看作一个完全背包问题呢让我们来拆解一下。在完全背包问题中我们有一个容量为V的背包和N种物品每种物品有无限个其体积为v_i。我们的目标是求出恰好装满背包的方案总数。现在我们把整数n看作是背包的总容量V。那么用来“装满”这个背包的“物品”是什么呢就是所有从1到n的正整数每个正整数i的体积就是它自身的值i并且每个数字i都可以被无限次使用因为在一个划分中数字1可以出现很多次。我们的目标就是求出用这些“物品”数字1, 2, 3, ..., n恰好装满容量为n的背包一共有多少种不同的方案。注意这里“不同方案”的定义在整数划分中12和21被视为同一种划分只关心组合不关心顺序而这恰好与完全背包问题中“不考虑物品放入顺序”的特性完美契合。如果考虑顺序那就变成了另一个问题“整数拆分”或“组合总和IV”。因此Acwing上的这道900题其核心价值不仅仅在于教会你如何计算一个具体的n的划分数更在于它提供了一个绝佳的“思维转换”案例和一套可以直接套用的“完全背包求方案数”的代码模板。掌握这个模板意味着你掌握了一类问题的通用解法。接下来我将带你从零开始彻底吃透这个模板背后的原理、实现细节、以及那些容易踩坑的地方。2. 完全背包求方案数的动态规划核心框架要理解模板必须先理解其背后的状态定义和转移方程。这是动态规划的灵魂也是写出正确、高效代码的基础。2.1 状态定义dp[i][j]的两种视角对于完全背包求方案数通常有两种常见的状态定义方式它们最终是等价的但思考角度略有不同理解这两种视角能让你更灵活地应对变种问题。视角一经典背包定义这是最直接、最符合背包问题原始模型的定义。dp[i][j]表示只考虑前i个物品即数字1到i恰好能组成总和为j的方案数。这里i的取值范围是1到nj的取值范围是0到n。初始状态dp[0][0] 1。这表示“考虑0个物品组成总和0”有一种方案即什么都不选。这是一个非常重要的边界条件是所有方案数的起点。对于其他的dp[0][j] (j0)值都为0因为不用任何数字无法组成正数。视角二更贴近整数划分的定义有些资料会采用另一种定义它更直观地对应了“用哪些数来划分”。dp[i][j]表示总和为i并且划分中最大的数不超过j的方案数。这个定义在思考状态转移时是从“最后一个数是多少”来切入的。最终答案就是dp[n][n]。这种定义方式在推导转移方程时会自然地引出一个包含min操作的优化但初学者理解起来可能稍显绕口。在本文中我们将主要采用第一种经典背包视角因为它与完全背包的模板直接对应更容易记忆和推广。2.2 状态转移方程从“最后一个数”入手基于视角一dp[i][j]考虑前i个数组成j的方案数我们来推导状态是如何转移的。对于当前状态dp[i][j]我们考虑最后一个或者说最新一次考虑加入的数字是什么。这里有两种情况完全不使用数字i那么组成总和j的方案完全来自于前i-1个数字。即dp[i-1][j]。至少使用一次数字i既然我们使用了至少一个i那么我们可以先从总和j中减去这个i看看剩下的部分j-i是如何组成的。而剩下的部分j-i依然可以使用前i个数字因为数字i无限个来组成。因此这部分方案数就是dp[i][j-i]。这里有一个关键点为什么第二种情况是dp[i][j-i]而不是dp[i-1][j-i]因为在我们决定放入一个i之后剩余的容量j-i仍然允许我们继续放入数字i。这体现了“完全背包”中物品无限取用的特性。如果是01背包这里就会是dp[i-1][j-i]表示放入一个i后剩下的容量只能用前i-1种物品来填。因此状态转移方程为dp[i][j] dp[i-1][j] dp[i][j-i]这个方程就是整个算法的核心。它简洁地表达了组成j的方案要么来自不用i的方案要么来自用了至少一个i的方案。2.3 初始化与最终答案初始化如前所述dp[0][0] 1。我们可以将dp数组初始化为全0然后单独设置这个起点。最终答案当我们考虑完所有数字从1到n并且要组成总和n时答案就是dp[n][n]。3. 代码实现从二维到一维的空间优化理解了状态方程代码实现就是水到渠成。我们将从最直观的二维数组开始然后优化到更高效的一维数组这是面试和竞赛中的必备技能。3.1 二维DP实现最直观的理解#include iostream using namespace std; const int N 1010, MOD 1e9 7; // 题目通常要求对一个大数取模防止溢出 int dp[N][N]; int main() { int n; cin n; // 初始化 dp[0][0] 1; // 前0个数组成0有1种方案空集 // 状态转移 for (int i 1; i n; i) { // 枚举物品数字 for (int j 0; j n; j) { // 枚举背包容量总和 // 不选数字i dp[i][j] dp[i-1][j] % MOD; // 如果容量允许考虑选数字i if (j i) { dp[i][j] (dp[i][j] dp[i][j - i]) % MOD; } } } cout dp[n][n] endl; return 0; }这段代码完全复现了我们的推导过程。两层循环时间复杂度是 O(n²)空间复杂度也是 O(n²)。对于n1000的典型题目范围这个复杂度是可以接受的。但是我们注意到在计算dp[i][j]时它只依赖于dp[i-1][j]和dp[i][j-i]。dp[i-1][j]是上一行同列的值dp[i][j-i]是本行左侧的值。这个依赖关系使得我们有可能将二维数组压缩成一维数组。3.2 一维DP优化滚动数组的精髓空间优化的关键在于我们发现更新dp[i][j]时只需要用到当前正在计算的这一行i的数据以及上一行i-1的个别数据。我们可以只用一个一维数组dp[j]来表示“在当前考虑的数字下组成总和j的方案数”。那么如何更新呢 回顾方程dp[i][j] dp[i-1][j] dp[i][j-i]在一维数组中dp[i-1][j]就是本轮更新之前dp[j]的值因为它来自上一轮i-1的计算结果。dp[i][j-i]是dp[j-i]并且由于我们是从小到大遍历j的当计算到dp[j]时dp[j-i]已经在本轮被更新过了因为j-i j。这正好对应了dp[i][j-i]而不是dp[i-1][j-i]因此一维状态下的更新公式就是dp[j] dp[j] dp[j-i]当j i时这里等号右边的dp[j]是“旧值”对应二维的dp[i-1][j]等号右边的dp[j-i]是“已经在本轮更新过的新值”对应二维的dp[i][j-i]。代码实现如下#include iostream using namespace std; const int N 1010, MOD 1e9 7; int dp[N]; int main() { int n; cin n; dp[0] 1; // 组成总和0的方案数为1空方案 for (int i 1; i n; i) { // 枚举物品数字1到n for (int j i; j n; j) { // 枚举容量从i开始因为ji时不可能选i dp[j] (dp[j] dp[j - i]) % MOD; } } cout dp[n] endl; return 0; }这就是最终的精简模板。它的核心在于dp[0] 1是“种子”所有方案都从这个空方案生长出来。外层循环i遍历所有可用的数字。内层循环j正向遍历从i到n。这是“完全背包”一维优化的关键标志如果是01背包内层循环需要反向遍历从n到i以确保每个物品只被使用一次。正向遍历则允许物品被重复使用。状态转移dp[j] dp[j-i]的含义是新的、包含数字i的、组成总和j的方案可以通过在那些组成总和为j-i的方案后面直接追加一个i来得到。一个重要的对比记忆点完全背包求方案数/最大价值一维数组内层循环正向遍历。01背包求方案数/最大价值一维数组内层循环反向遍历。 这个区别的根本原因在于状态转移方程中是依赖于dp[i][j-i]本行需要先更新还是dp[i-1][j-i]上一行需要后更新。4. 模板的深度剖析与常见问题排查虽然代码只有短短十行但其中蕴含的细节和可能遇到的问题却不少。下面我们来逐一拆解。4.1 为什么内层循环从i开始在优化后的代码中内层循环是for (int j i; j n; j)。这是因为当背包容量j小于当前数字i时根本不可能选择这个数字所以dp[j]的值不会因为数字i的引入而改变它直接继承自上一轮即只考虑前i-1个数字时的值。由于我们用的是一维数组这个“继承”是自动发生的dp[j]在进入本轮i的循环时存储的就是上一轮的值。所以直接从j i开始遍历可以略过无效操作并且能避免j-i出现负数索引的情况。4.2 取模操作的位置与溢出风险题目通常要求结果对1e97取模。这里有两个细节在加法后立即取模dp[j] (dp[j] dp[j - i]) % MOD;括号是必须的。因为两个int相加可能溢出先取模再赋值给int是安全的。1e97是一个质数也是常用的模数。dp数组的数据类型使用int通常是足够的因为每次运算后都取了模值会保持在[0, MOD-1]范围内。但在某些极端情况或中间计算过程中如果没及时取模int可能会溢出。更稳妥的做法是使用long long来声明dp数组或者在加法时进行强制转换dp[j] (dp[j] 0LL dp[j - i]) % MOD;其中的0LL会将整个表达式提升为long long类型进行计算然后再取模赋值回int。这是竞赛中一种常见的防溢出技巧。4.3 初始化dp[0] 1的深刻含义这是最容易出错的地方之一。dp[0] 1表示“组成总和0的方案有1种”即“空方案”或“什么都不选”。这个初始值是整个动态规划的基石。为什么必须是1而不是0让我们考虑最小的例子n1。我们只有一个数字1。当i1j1时状态转移dp[1] dp[1] dp[0]。初始时dp[1]是0。如果dp[0]也是0那么dp[1]将永远是0这显然不对因为用数字1组成总和1明明有1种方案。只有当dp[0] 1时dp[1] 0 1 1才能得到正确结果。从组合意义上理解任何一个合法的划分都可以看作是从“空状态”开始不断地往里面添加数字i而得到的。dp[0]1就是这个过程的起点。4.4 与“组合总和IV”问题的本质区别LeetCode上有一道题“377. 组合总和IV”题目描述也是给定一些数字可重复使用和一个目标数求有多少种组合方式。很多初学者会混淆它和“整数划分”。它们的核心区别在于整数划分本题12和21被视为同一种方案。求的是“组合”数。组合总和IV12和21被视为不同的方案。求的是“排列”数。这个区别直接导致了动态规划状态转移的不同。对于求“组合”数整数划分我们的外层循环是遍历“物品”数字内层循环遍历“容量”。这保证了在考虑方案时数字的顺序是被固定的按物品顺序考虑不会产生(1,2)和(2,1)两种记录。对于求“排列”数组合总和IV我们的外层循环是遍历“容量”内层循环遍历“物品”。这样对于同一个容量j我们会考虑所有物品放在最后一个位置的可能性从而产生了顺序。如果你用本题的模板去解“组合总和IV”会得到错误的结果。反之亦然。理解这个差异能帮助你真正把握动态规划中“顺序”这一微妙而关键的概念。5. 实战扩展当划分要求发生变化时模板是死的问题是活的。整数划分问题有很多变种掌握核心思想后我们可以轻松应对。5.1 变种一划分成若干个不同整数如果要求划分出的所有正整数必须互不相同即每个数字最多用一次那么问题就变成了“01背包求方案数”。此时状态定义不变但状态转移方程需要修改。因为每个数字i最多只能用一次所以当我们要从“使用了数字i”这个状态转移时应该从dp[i-1][j-i]转移过来表示在没使用i之前即前i-1个数组成了j-i。二维方程变为dp[i][j] dp[i-1][j] dp[i-1][j-i]当j i 一维优化后内层循环需要逆序遍历j从n到i以确保dp[j-i]使用的是上一轮i-1的值。// 划分成不同整数的一维01背包解法 dp[0] 1; for (int i 1; i n; i) { for (int j n; j i; j--) { // 逆序遍历 dp[j] (dp[j] dp[j - i]) % MOD; } } cout dp[n] endl;5.2 变种二划分成奇数个或偶数个正整数这类问题通常需要增加一维状态来记录“划分的个数”。例如求将n划分成恰好k个正整数的方案数。我们可以定义dp[i][j]为用前i个数字组成总和为j且恰好用了i个数字的方案数注意这里的i含义可能变化通常我们会增加一维。更通用的定义是dp[j][k]表示组成总和为j且恰好由k个数字构成的方案数。 其状态转移可以考虑最后一个数字是多少dp[j][k] dp[j-1][k-1] dp[j-k][k]这个方程需要一些组合数学的推导它来自于另一种经典的整数划分DP思路Ferrers图。它表示一个和为j、个数为k的划分要么其最小的数是1那么去掉这个1就变成了和为j-1、个数为k-1的划分要么其所有的数都大于1那么给每个数都减去1就变成了和为j-k、个数仍为k的划分。5.3 变种三结果对大数取模的注意事项我们之前的模板已经处理了取模。但在一些更复杂的变种或自己推导方程时要特别注意加法和乘法取模(a b) % MOD和(a * b) % MOD。减法取模(a - b MOD) % MOD防止出现负数。初始化与取模初始值1也要在取模的意义下理解。6. 调试技巧与思维验证如何确保你的DP是正确的对于动态规划尤其是状态压缩后的一维DP写出代码后心里没底是常事。以下是我常用的验证方法小数据暴力对拍写一个最简单的DFS暴力搜索程序枚举所有可能的划分用于计算n较小比如n 20时的答案。然后用你的DP程序跑同样的n对比结果是否一致。这是最可靠的方法。打印DP表在二维DP实现中在循环结束后打印出整个dp数组。观察数据是否符合你的预期。例如dp[i][0]应该都是1组成0只有空方案dp[1][j]应该都是1只用数字1只有全1这一种方式组成任何j。对于一维DP你可以在每轮外层循环即考虑完数字i后打印出当前的dp数组观察它的变化。手动模拟用纸笔计算n1,2,3,4,5的情况。n5的答案应该是7。一步步跟着你的代码逻辑走看dp数组是如何从[1,0,0,0,0,0]最终变成[1,1,2,3,5,7]的这里是一维数组最终状态dp[0]到dp[5]。思考边界n0时答案应该是1空划分。你的程序处理n0的输入会输出1吗如果模数MOD设置错了或者没取模对于大的n输出可能是负数或奇怪的数。7. 从模板到精通理解本质方能举一反三“整数划分”的完全背包解法其威力在于它提供了一种将“无限选取的组合计数”问题转化为标准动态规划模型的范式。当你遇到以下类型的问题时都可以尝试套用或修改这个模板零钱兑换问题LeetCode 518给定不同面额的硬币无限个和一个总金额求凑成总金额的硬币组合数。这几乎是本题的“换皮”题硬币面额就是“物品体积”总金额就是“背包容量”。数字组合问题给定一个正整数集合可能不是连续的1到n和目标和求组合方式。这时只需要把外层循环遍历的“数字1到n”改成遍历给定的集合即可。带有限制条件的划分例如划分出的数字不能超过某个值m或者必须是某些特定数字。这通常只需要修改循环的边界条件或增加判断。记住模板代码是简单的但背后的状态定义、转移方程和优化原理才是核心。我个人的经验是不要死记硬背for循环的顺序和dp[j] dp[j-i]这行代码。而是每次遇到类似问题都从最基本的“状态定义”开始重新思考推导出二维的转移方程然后再考虑是否能优化成一维以及优化时遍历顺序应该如何。这个过程练多了这类问题就真的成了你的“模板”可以信手拈来。最后再分享一个我早期踩过的坑我曾混淆了“完全背包求方案数”和“完全背包求最大价值”的初始化。求最大价值时我们通常初始化dp[0]0其他为负无穷或0取决于问题。但求方案数时那个dp[0]1是灵魂所在它代表了“一种空方案”是后续所有方案得以累加的基石。一旦这里设错整个结果就全错了。所以每次写DP初始化时都要问自己一句“这个状态的初始物理意义是什么”想明白了代码自然就对了。