我的算法书 - 整数划分

一句话算法

整数划分用“是否使用至少一个 m”把问题分成两类。

问题模型

把正整数 n 表示成若干个正整数之和，且不区分顺序。

例如 6 的划分有：

6
5+1
4+2
4+1+1
3+3
3+2+1
3+1+1+1
2+2+2
2+2+1+1
2+1+1+1+1
1+1+1+1+1+1

所以答案是 11。

核心直觉

不区分顺序时，直接枚举加数很容易重复：

5 + 1
1 + 5

它们是同一种划分。

为了避免重复，我们规定划分中的每个数都不超过某个上限 m。

定义：

f(n,m) = \text{把 } n \text{ 划分成若干正整数，且每个数不超过 } m \text{ 的方案数}

现在考虑最大允许数字 m：

不使用 m：方案数是 f(n, m-1)。
至少使用一个 m：先拿走一个 m，剩下 n-m 仍然可以继续使用不超过 m 的数，方案数是 f(n-m, m)。

所以：

f(n,m)=f(n,m-1)+f(n-m,m)

算法步骤

如果 n == 0，说明刚好划分完成，返回 1。
如果 m == 0 且 n > 0，说明没有数字可用，返回 0。
如果 m > n，把 m 缩到 n，因为大于 n 的数不可能出现。
否则：
- 计算不使用 m 的方案 f(n, m - 1)。
- 计算至少使用一个 m 的方案 f(n - m, m)。
- 两者相加。
用 memo[n][m] 记录已经算过的状态。

算法证明

分类不重：

所有合法划分按“是否使用数字 m”分成两类：

第一类完全不使用 m。
第二类至少使用一个 m。

一个划分不可能同时属于两类，所以分类不重。

分类不漏：

任意一个合法划分，要么没有 m，要么至少有一个 m，必然属于其中一类，所以不漏。

子问题正确：

不使用 m 时，所有数都不超过 m-1，对应 f(n,m-1)。
至少使用一个 m 时，去掉一个 m 后，剩余和为 n-m，仍允许继续使用 m，对应 f(n-m,m)。

因此递推式正确。

复杂度分析

状态是 (n, m)，共有 $O(n^2)$ 个。

时间复杂度： $O(n^2)$ 。
空间复杂度： $O(n^2)$ 。

如果不用记忆化，递归会重复计算大量状态。

代码实现

cpp

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

        #include <bits/stdc++.h>
using namespace std;

const int maxn = 500 + 5;

long long memo[maxn][maxn];

// f(n, m): 把 n 划分成若干个正整数之和，且每个数不超过 m 的方案数。
long long f(int n, int m) {
    if (n == 0) return 1;
    if (m == 0) return 0;
    if (m > n) return f(n, n);
    if (memo[n][m] != -1) return memo[n][m];

    // 不使用 m 的方案 + 至少使用一个 m 的方案。
    memo[n][m] = f(n, m - 1) + f(n - m, m);
    return memo[n][m];
}

int main() {
    int n;
    cin >> n;
    memset(memo, -1, sizeof(memo));
    cout << f(n, n) << '\n';
    return 0;
}

测试用例

输入：

输出：

应用分类详解

整数划分的本质是“无序选择若干正整数凑出目标和”。

一、不区分顺序的计数

典型模式： a+b 和 b+a 算同一种方案。

识别信号： 划分、拆分、若干数之和、不考虑顺序。

核心建模： 给每个数设置最大上限，强制方案按非增或非降顺序出现。

二、完全背包计数的递归版

典型模式： 每种大小可以使用多次。

识别信号： 数字 1..n 每个可选任意次，求凑出总和的方案数。

核心建模： f(n,m) 和完全背包里的“前 m 种物品凑和为 n”是同一类状态。

三、记忆化搜索转 DP

典型模式： 递归状态有限，且重复出现。

识别信号： f(n,m) 被多个上层状态调用。

核心建模： 先写记忆化递归，再改成二维 DP 表。

经典例题

整数划分计数：标准 f(n,m) 模型。
luogu-P1025 数的划分：固定分成 k 份，是整数划分的常见变体。
luogu-P1832 A+B Problem：完全背包计数视角。

参考

本书相关章节：完全背包