企业官网建设流程全解析

第一次在 AcWing 上遇到整数划分这道题时，我心想：这不就是组合问题嘛，DFS 枚举一下就能出答案。结果 n 到 30 左右程序就开始卡顿，n 到 100 直接没法看。后来才明白，这道题的定位是计数类 DP，它要的不是某一套具体拆分方案，而是所有不同拆法的数量，同时还要求拆出的序列不区分顺序。所谓整数划分，就是给定一个正整数 n，把它拆成若干个正整数的和，每种"若干个正整数"的集合算一种方案。比如 5 可以拆成 5、4+1、3+2、3+1+1、2+2+1、2+1+1+1、1+1+1+1+1，一共 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) 非递增，是为了去掉顺序重复。也就是说 2+1 和 1+2 算同一种方案，只允许写成 2+1 这种形式。这个"非递增"的约定，既是枚举阶段用于剪枝的抓手，也是 DP 阶段用于去重的关键。

很多第一次接触这道题的人，包括我，第一反应就是 DFS：

• 从大到小枚举下一个数，保证下一个数不超过当前数；
• 累加和，等于 n 就计数，大于 n 就剪枝；
• 找到一种方案后返回，继续搜索。

n 小的时候，这个思路跑 n=5、n=10 都挺快，答案也能对上。但一旦 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 的物品各选一件，无论以什么顺序"放入"，都是同一组物品组合，对应到整数划分就是 2+1 这一种方案。

定义状态 (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^9+7 ]

这里内层循环必须正序。原因完全背包里讲过：正序遍历时，(f[j-i]) 可能已经被当前这一轮物品更新过，等于允许同一个物品被选多次；而如果内层逆序，(f[j-i]) 还是上一轮的状态，就退化成 01 背包了，每个数字最多只能选一次。整数划分里数字是可以重复出现的，比如 1+1+1+1+1，所以必须正序。

举个例子，n=3 时：

• 初始化 (f[0] = 1)，其余为 0；
• 用数字 1 更新：(f[1]=1，f[2]=1，f[3]=1)；
• 用数字 2 更新：(j=2) 时 (f[2] = 1 + f[0] = 2)，(j=3) 时 (f[3] = 1 + f[1] = 2)；
• 用数字 3 更新：(j=3) 时 (f[3] = 2 + f[0] = 3)。

最终 (f[3] = 3)。这对应 3 的划分：3、2+1、1+1+1，刚好 3 种，完美对上。

2.3 为什么这题的答案就是 f[n]

有些读者可能会疑惑：完全背包的枚举顺序是固定的，这样不会漏掉某个划分吗？比如 1+2 和 2+1 算同一种，但完全背包枚举物品时，先处理 1 再处理 2，是不是只保留了"小的数先出现"的组合？

实际上，完全背包的组合状态天然就是无序的。(f[j]) 只记录"选了哪些数字"，不记录"选入的路径顺序"。当我们枚举到数字 (i) 时，选择它一次，方案数就转移到新的总和上，多条路径最终落在同一个状态时，贡献会被合并，而不是各算各的。这种"合并"恰恰就是计数类 DP 需要的行为。

所以我个人建议，忘记"先选谁后选谁"这类描述，完全背包的维度本质上就是"可用物品集合"和"容量"两个维度。外层枚举物品，是在不断扩大可用集合；内层枚举容量，是在计算当前可用集合下各个容量的方案数。这个视角更接近 DP 状态定义本身。

3. 解法二：按最小元素分类的计数思想

3.1 换一种状态定义：总和 + 个数

完全背包的思路固然直观，但 AcWing 上还有另一种很漂亮的计数类 DP 思路，很多题解也用它做"标准解法"。

定义 (dp[i][j]) 表示：把正整数 (i) 拆成恰好 (j) 个正整数之和的方案数，拆分仍然不区分顺序。注意，这里多了一个维度"个数 (j)"。

比如 (dp[5][2] = 2)，因为 5 拆成 2 个数有 4+1 和 3+2 两种；(dp[5][3] = 2)，因为 5 拆成 3 个数有 3+1+1 和 2+2+1 两种。

最终答案就是：

[ \sum_{j=1}^{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 手动跑一遍 n=5 的 DP 表

光看公式不够直观，我手动推一遍 n=5 的二维表。

初始化：(dp[0][0] = 1)，其余为 0。循环时 i 从 1 到 5，j 从 1 到 i。

以 (dp[5][3]) 为例，它等于 (dp[4][2] + dp[2][3])。(dp[4][2]=2)，对应含 1 时去掉 1 得到 4 拆 2 个数的两种（3+1、2+2），加回 1 就是 3+1+1、2+2+1 两种；(dp[2][3]=0)，因为 3 > 2 无法拆成 3 个数，不含 1 的情况不存在。

最终把所有 (dp[5][j]) 加起来：1+2+2+1+1=7，与手算结果一致。

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 个 1；j 超过 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^9+7 + 10^9+7) 算出来大约是 (2*10^9)，还在 int 范围边缘，但两个大数相加，或者一个状态累加多次时，就可能超过 int 上限。稳妥的做法是：

• 加法后立刻取模；
• 或者用 long long 临时接收加法结果。

二维解法里最后统计答案时会累加很多项，我用 long long 来接 ans，再每步取模。这也是一个小优化点，建议抄代码时顺手加上。

5.3 打印 DP 表：最有效的定位手段

如果你写完后答案不对，别急着怀疑公式，先打印小 n 的 DP 表。比如 n=6 时，正确的划分总数应该是 11，n=7 是 15，n=8 是 22。你可以把 n 改成 5，打印出 (f[0..5]) 或者 dp 表，和手算的期望值逐项对照。

以完全背包解法为例，n=5 时，最终 (f[5]) 应该是 7。如果中间某个值偏大或偏小，多半是循环顺序搞反了。检验顺序最直接的方法是：把内层循环从正序改成逆序，跑出来的结果会立刻变小，因为每个数字只能用一次，方案数自然少了。看到这个差异，基本就能锁定问题。

二维解法打印表时，建议把每一行 (j=1..i) 都打印出来。我上面给出的 n=5 的表就是很好的参考答案，打印出来一比对，哪里错就一目了然。

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)^{k+1} p(n - \frac{k(3k-1)}{2}) ]

其中 (k) 取正整数和负整数。这个结论虽然看起来神奇，但背后的生成函数推导非常优美。如果以后遇到 n 达到 (10^5) 甚至更大的整数划分题，用完全背包 (O(n^2)) 会超时，这个时候就可以搬出五边形数定理。

我个人在学这道题的时候，最大的收获不是背下了两个代码模板，而是理解了"为什么 DP 能自动去重"。答案在于状态定义本身就不关心排列顺序，而集合划分的互斥性保证了同一个方案不会在多个分支里被重复统计。这个思想，比记住任何一个具体的转移方程都重要。以后你看到任何计数类 DP，先问自己：我能不能找到一个维度的划分，让每个合法对象恰好落入一类？如果能，转移方程基本上就水到渠成了。