整数划分的计数类DP：从完全背包到最小元素分类

第一次在 AcWing 上遇到整数划分这道题时我心想这不就是组合问题嘛DFS 枚举一下就能出答案。结果 n 到 30 左右程序就开始卡顿n 到 100 直接没法看。后来才明白这道题的定位是计数类 DP它要的不是某一套具体拆分方案而是所有不同拆法的数量同时还要求拆出的序列不区分顺序。所谓整数划分就是给定一个正整数 n把它拆成若干个正整数的和每种若干个正整数的集合算一种方案。比如 5 可以拆成 5、41、32、311、221、2111、11111一共 7 种。在 AcWing 算法基础课里这题常被当作计数类 DP 的入门例题搞懂它后面碰到的数字组合、完全背包计数、括号序列计数等问题都会顺很多。这篇文章我会从两条不同的 DP 思路展开一条是从完全背包的角度理解一条是从最小元素分类的角度推导。两条路都能 AC但思维方式和代码细节差别挺大。我会把状态定义、转移方程、初始化、滚动数组的坑、以及调试时怎么验证答案对不对都讲清楚。中途还会手算几个小例子把 DP 表摊开看方便你理解每个下标到底是怎么来的。1. 从 DFS 到 DP为什么暴力枚举一定没戏1.1 先给问题一个精确的数学定义整数划分的严格说法是把正整数 n 写成 (n n_1 n_2 \dots n_k)其中 (k \ge 1)且 (n_1 \ge n_2 \ge \dots \ge n_k \ge 1)。这里规定 (n_i) 非递增是为了去掉顺序重复。也就是说 21 和 12 算同一种方案只允许写成 21 这种形式。这个非递增的约定既是枚举阶段用于剪枝的抓手也是 DP 阶段用于去重的关键。很多第一次接触这道题的人包括我第一反应就是 DFS从大到小枚举下一个数保证下一个数不超过当前数累加和等于 n 就计数大于 n 就剪枝找到一种方案后返回继续搜索。n 小的时候这个思路跑 n5、n10 都挺快答案也能对上。但一旦 n 到了 100指数级别的搜索直接爆炸。原因在于允许拆出的数种类是 1 到 n每一步可选的数规模都没法有效压缩剪枝条件只是不大于上一个数这个约束在大 n 面前太弱了。1.2 计数类 DP 和普通 DP 的关键差异在整数划分这个场景里我们只关心方案数量不关心具体方案长什么样。这和求最大价值的背包问题有本质区别背包问题是从若干物品中选价值最大每一步用 max 做决策而计数类问题要求的是总共有多少种选法状态转移里用的是加法把不同来源的方案数累加起来。这里最核心的是不重不漏。DP 转移本质上在对集合做划分划分出的两个子集必须互不相交不重同时它们要能覆盖所有情况不漏。以整数划分来说我们常见的做法是固定拆分后的最大值或者固定最小值让每一种划分方案只属于一个子集这样才不会出现同一方案被重复计算的情况。从 DFS 到 DP 的转折点就是把下一个数选谁这个依赖具体方案的问题转换成只记录当前状态有多少种方案。比如我们可以问用不超过某个上限的数凑出某个总和一共有多少种方式一旦把状态定义成值和值之间的关系就可以放心地递推了。这也就是为什么 AcWing 上这题会被归入计数类 DP而不是简单的搜索题。2. 解法一把它当成完全背包来做2.1 状态定义与转移方程第一种经典思路是把整数划分看成一个完全背包问题。我们可以把数字 1、2、3、...、n 分别看作体积为 1、2、3、...、n 的物品每种物品有无限多个背包容量是 n。问有多少种方式恰好装满背包。这里有个很有意思的点顺序问题。背包问题天然不关心物品放入背包的先后顺序它只关心选了几个、每个选了多深。这正好契合整数划分中不区分顺序的要求。比如体积 2 的物品和体积 1 的物品各选一件无论以什么顺序放入都是同一组物品组合对应到整数划分就是 21 这一种方案。定义状态 (dp[i][j]) 表示只考虑使用数字 (1, 2, \dots, i) 时凑出总和 (j) 的方案数。转移时我们把来源分成两类不使用数字 (i)此时方案数就是 (dp[i-1][j])至少使用一个数字 (i)先拿走一个 (i)剩下需要用 (1, \dots, i) 去凑出 (j-i)方案数是 (dp[i][j-i])。所以[ dp[i][j] dp[i-1][j] dp[i][j-i] ]这个式子非常像完全背包的经典转移区别是普通完全背包求价值时取 max这里变成了加法。初始状态是 (dp[0][0] 1)表示什么都不选、总和为 0算一种方案。2.2 二维转一维优化的正确姿势由于 (i) 这一维只依赖当前行和上一行我们可以像完全背包一样把二维数组压缩成一维。设一维数组 (f[j]) 表示凑出总和 (j) 的方案数。我们在外层枚举物品 (i)内层从 (i) 到 (n) 枚举容量 (j)更新[ f[j] (f[j] f[j-i]) \bmod 10^97 ]这里内层循环必须正序。原因完全背包里讲过正序遍历时(f[j-i]) 可能已经被当前这一轮物品更新过等于允许同一个物品被选多次而如果内层逆序(f[j-i]) 还是上一轮的状态就退化成 01 背包了每个数字最多只能选一次。整数划分里数字是可以重复出现的比如 11111所以必须正序。举个例子n3 时初始化 (f[0] 1)其余为 0用数字 1 更新(f[1]1f[2]1f[3]1)用数字 2 更新(j2) 时 (f[2] 1 f[0] 2)(j3) 时 (f[3] 1 f[1] 2)用数字 3 更新(j3) 时 (f[3] 2 f[0] 3)。最终 (f[3] 3)。这对应 3 的划分3、21、111刚好 3 种完美对上。2.3 为什么这题的答案就是 f[n]有些读者可能会疑惑完全背包的枚举顺序是固定的这样不会漏掉某个划分吗比如 12 和 21 算同一种但完全背包枚举物品时先处理 1 再处理 2是不是只保留了小的数先出现的组合实际上完全背包的组合状态天然就是无序的。(f[j]) 只记录选了哪些数字不记录选入的路径顺序。当我们枚举到数字 (i) 时选择它一次方案数就转移到新的总和上多条路径最终落在同一个状态时贡献会被合并而不是各算各的。这种合并恰恰就是计数类 DP 需要的行为。所以我个人建议忘记先选谁后选谁这类描述完全背包的维度本质上就是可用物品集合和容量两个维度。外层枚举物品是在不断扩大可用集合内层枚举容量是在计算当前可用集合下各个容量的方案数。这个视角更接近 DP 状态定义本身。3. 解法二按最小元素分类的计数思想3.1 换一种状态定义总和 个数完全背包的思路固然直观但 AcWing 上还有另一种很漂亮的计数类 DP 思路很多题解也用它做标准解法。定义 (dp[i][j]) 表示把正整数 (i) 拆成恰好 (j) 个正整数之和的方案数拆分仍然不区分顺序。注意这里多了一个维度个数 (j)。比如 (dp[5][2] 2)因为 5 拆成 2 个数有 41 和 32 两种(dp[5][3] 2)因为 5 拆成 3 个数有 311 和 221 两种。最终答案就是[ \sum_{j1}^{n} dp[n][j] ]因为 n 不管拆成几个数都是一种划分把这些情况加起来即可。3.2 从有没有数字 1入手推导转移方程现在考虑 (dp[i][j])。任意一种划分要么含有数字 1要么不含数字 1两者必居其一而且不可能同时发生。这个二分就是集合划分的核心。第一种情况划分中含有数字 1。由于划分不区分顺序我们可以把 1 放在最前面或最后面。不管怎么放把那个 1 从划分里拿掉剩下的是总和为 (i-1)、恰好被分成 (j-1) 个数的划分。反过来任意一个 (i-1) 拆成 (j-1) 个数的划分只要加上一个 1就得到 (i) 拆成 (j) 个数且含 1 的划分。所以这部分方案数就是 (dp[i-1][j-1])。第二种情况划分中不含数字 1。这意味着这 (j) 个数每个都至少是 2。我们可以把每个数都减去 1那么总和变成 (i-j)个数仍然不变还是 (j) 个。每个数减 1 之后大小至少是 1所以这对应的是把 (i-j) 拆成 (j) 个正整数的一种划分。反过来把任意一种 (i-j) 拆成 (j) 个数的划分每个数加 1就能得到一种 (i) 拆成 (j) 个数且不含 1 的划分。于是转移方程是[ dp[i][j] dp[i-1][j-1] dp[i-j][j] ]注意第二项只有在 (i-j) 仍然能够拆成 (j) 个正整数时才有效也就是 (i-j \ge j)。如果 (i-j j)说明不存在每个数至少 2、还要分成 j 个数的划分第二项就当 0 处理。这个有 1/无 1的分类方式是最能体现计数类 DP不重不漏思想的。为什么不会重复因为一个划分要么有 1要么没有 1这两类是互斥的。为什么不会漏因为每一个划分必然属于其中一类。3.3 手动跑一遍 n5 的 DP 表光看公式不够直观我手动推一遍 n5 的二维表。初始化(dp[0][0] 1)其余为 0。循环时 i 从 1 到 5j 从 1 到 i。(dp[i][j])j1j2j3j4j5i110000i211000i311100i412110i512211以 (dp[5][3]) 为例它等于 (dp[4][2] dp[2][3])。(dp[4][2]2)对应含 1 时去掉 1 得到 4 拆 2 个数的两种31、22加回 1 就是 311、221 两种(dp[2][3]0)因为 3 2 无法拆成 3 个数不含 1 的情况不存在。最终把所有 (dp[5][j]) 加起来122117与手算结果一致。4. 两套代码对比与 AC 细节4.1 完全背包一维代码#include iostream using namespace std; const int N 1010; const int MOD 1e9 7; int f[N]; int main() { int n; cin n; f[0] 1; for (int i 1; i n; i) { for (int j i; j n; j) { f[j] (f[j] f[j - i]) % MOD; } } cout f[n] endl; return 0; }这里的 (f[0]1) 是非常经典的起点空集合凑出总和 0算一种方案。没有这个初始化所有结果都会是 0。内层从 i 开始是因为 j i 时 (j-i) 是负数不合法同时对于当前数字 i容量小于 i 也不可能选它。4.2 最小元素分类的二维代码#include iostream using namespace std; const int N 1010; const int MOD 1e9 7; int dp[N][N]; int main() { int n; cin n; dp[0][0] 1; for (int i 1; i n; i) { for (int j 1; j i; j) { dp[i][j] dp[i - 1][j - 1]; if (i - j j) { dp[i][j] (dp[i][j] dp[i - j][j]) % MOD; } } } long long ans 0; for (int j 1; j n; j) { ans (ans dp[n][j]) % MOD; } cout ans endl; return 0; }第二维 j 最大只能到 i因为 i 至少拆成 i 个 1j 超过 i 时方案数为 0。这里的边界if (i - j j)就是为了处理不含 1 的分支防止给一个无意义的负数下标状态做加法。两种解法的复杂度都是 (O(n^2))在 AcWing 900 的 n ≤ 1000 数据范围内完全没有压力。取模时每次加法后及时取模避免中间结果溢出。4.3 两种状态定义有什么本质差别如果只看代码两种解法的差别好像只是状态维度定义不同。但实际上它们代表了两种不同的数学视角完全背包视角数字是物品关注的是可选数字集合大小和总和这两个量。维度是数字范围 总和。最小元素分类视角关注的是总和和拆成几部分这两个量。维度是总和 份数。这两种视角分别对应整数划分问题的两个经典研究方向。组合数学里第一部分对应有受限部件的拆分数第二部分对应按拆分数量的统计。很多高级划分问题比如把 n 拆成若干不同正整数之和、拆成奇数个数的和用这两种视角都能找到切入点。因此做完这题之后如果能把两个转移方程都理解透后面做其他计数题会很有底气。5. 踩坑记录初始化、取模与调试技巧5.1 初始化一错满盘皆输第一个常见的坑是完全背包的 (f[0])。一定要赋值为 1否则所有转移都是 0。有些同学会把它写成 (f[0] 0)理由是凑出总和 0 不需要任何数字。但这里我们统计的是有多少种凑法什么都没选就是一种方案所以是 1。第二个坑是二维解法里的 (dp[0][0])。同理它也是 1。还有一种常见的初始化方式是直接把整个 dp 数组清零然后单独设置dp[0][0] 1。如果漏了这一行(dp[1][1]) 会从 (dp[0][0]) 取到一个 0导致后面所有结果都失真。5.2 取模的时机和方法这题要求的答案对 (10^9 7) 取模所以每次加法之后取模即可。要注意 C 的 int 溢出。虽然 (10^97 10^97) 算出来大约是 (2*10^9)还在 int 范围边缘但两个大数相加或者一个状态累加多次时就可能超过 int 上限。稳妥的做法是加法后立刻取模或者用 long long 临时接收加法结果。二维解法里最后统计答案时会累加很多项我用 long long 来接 ans再每步取模。这也是一个小优化点建议抄代码时顺手加上。5.3 打印 DP 表最有效的定位手段如果你写完后答案不对别急着怀疑公式先打印小 n 的 DP 表。比如 n6 时正确的划分总数应该是 11n7 是 15n8 是 22。你可以把 n 改成 5打印出 (f[0..5]) 或者 dp 表和手算的期望值逐项对照。以完全背包解法为例n5 时最终 (f[5]) 应该是 7。如果中间某个值偏大或偏小多半是循环顺序搞反了。检验顺序最直接的方法是把内层循环从正序改成逆序跑出来的结果会立刻变小因为每个数字只能用一次方案数自然少了。看到这个差异基本就能锁定问题。二维解法打印表时建议把每一行 (j1..i) 都打印出来。我上面给出的 n5 的表就是很好的参考答案打印出来一比对哪里错就一目了然。6. 从这道题延伸出去的几个思考方向6.1 怎么输出一种具体划分方案如果题目要求输出任意一种划分而不是计数那么 DP 表仍然有用。比如完全背包解法里我们可以从 n 往回追溯当 (f[j]) 是从 (f[j-i]) 转移来时记录一个数 i然后继续回溯 (j-i)。当然因为有多种转移路径输出的方案不唯一但只要按 DP 表的转移来源回溯就一定能得到一种合法划分。6.2 加限制条件的变体整数划分问题的变体非常丰富。如果限制每个数不能超过 m完全背包视角下只需要把外层枚举的数字范围改成 1 到 m。如果限制拆分结果中 1 的个数必须是偶数二维解法中只要在转移时加上对 1 个数的约束即可。这类问题在信息学竞赛和面试题里经常出现本质上都是对不重不漏集合划分的考察。6.3 更大规模怎么优化经典整数划分问题还有一个著名的优化方向利用欧拉五边形数定理可以在 (O(n\sqrt{n})) 时间内求出拆分数而不需要两层循环。这个公式是[ p(n) \sum_{k \ne 0} (-1)^{k1} p(n - \frac{k(3k-1)}{2}) ]其中 (k) 取正整数和负整数。这个结论虽然看起来神奇但背后的生成函数推导非常优美。如果以后遇到 n 达到 (10^5) 甚至更大的整数划分题用完全背包 (O(n^2)) 会超时这个时候就可以搬出五边形数定理。我个人在学这道题的时候最大的收获不是背下了两个代码模板而是理解了为什么 DP 能自动去重。答案在于状态定义本身就不关心排列顺序而集合划分的互斥性保证了同一个方案不会在多个分支里被重复统计。这个思想比记住任何一个具体的转移方程都重要。以后你看到任何计数类 DP先问自己我能不能找到一个维度的划分让每个合法对象恰好落入一类如果能转移方程基本上就水到渠成了。