第一次见到”整数划分”是在一道计数题里，当时完全没头绪，手写了 n=4 的划分才算看懂定义。说白了，就是把一个正整数拆成若干个正整数之和，顺序不同、数字相同算同一种。这篇把定义、递归实现和 DP 优化一起记下来。

整数的划分（Partition of an Integer）详解

1. 什么是整数划分

简单说，整数划分就是把一个正整数表示成一系列正整数之和，顺序不同但数字相同的算同一种划分。例如：

• 4的划分有：
  • 4
  • 3 + 1
  • 2 + 2
  • 2 + 1 + 1
  • 1 + 1 + 1 + 1

2. 递归方法实现

方法一：不考虑顺序的划分

#include <iostream>
using namespace std;

// 计算整数n的划分数，最大加数不超过m
int partition(int n, int m) {
    if (n == 0) return 1;  // 基本情况：0只有一种划分方式
    if (m == 0) return 0;  // 没有可用的加数
    if (n < m) return partition(n, n);  // 最大加数不能超过n本身
    // 划分中包含m的情况 + 不包含m的情况
    return partition(n - m, m) + partition(n, m - 1);
}

int main() {
    int n = 4;
    cout << "整数 " << n << " 的划分数为: " << partition(n, n) << endl;
    return 0;
}

方法二：输出所有划分方式

#include <iostream>
#include <vector>
using namespace std;

void printPartitions(int n, int max, vector<int>& current) {
    if (n == 0) {
        // 找到一个划分，输出它
        for (int i = 0; i < current.size(); i++) {
            if (i != 0) cout << "+";
            cout << current[i];
        }
        cout << endl;
        return;
    }

    for (int i = min(max, n); i >= 1; i--) {
        current.push_back(i);
        printPartitions(n - i, i, current);
        current.pop_back();
    }
}

int main() {
    int n = 4;
    vector<int> current;
    cout << "整数 " << n << " 的所有划分方式:" << endl;
    printPartitions(n, n, current);
    return 0;
}

3. 动态规划方法实现

递归版本是指数级的，n 稍微大一点就明显变慢，我当时就吃过这个亏，所以换 DP：

#include <iostream>
#include <vector>
using namespace std;

int countPartitionsDP(int n) {
    vector<vector<int>> dp(n + 1, vector<int>(n + 1, 0));

    // 基本情况
    for (int i = 0; i <= n; i++) {
        dp[0][i] = 1;  // 0只有一种划分方式
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (j > i) {
                dp[i][j] = dp[i][i];
            } else {
                dp[i][j] = dp[i - j][j] + dp[i][j - 1];
            }
        }
    }

    return dp[n][n];
}

int main() {
    int n = 4;
    cout << "整数 " << n << " 的划分数为: " << countPartitionsDP(n) << endl;
    return 0;
}

4. 算法分析

• 时间复杂度：

  • 递归方法：O(2^n)（指数级）
  • 动态规划：O(n^2)（多项式级）

• 空间复杂度：

  • 递归方法：O(n)（调用栈深度）
  • 动态规划：O(n^2)（二维数组）

5. 应用场景

当时我查了一下，这问题还不只是用来出题的，下面这些领域都会碰到它：

• 组合数学
• 统计学中的分组问题
• 计算机科学中的资源分配问题
• 数论研究

6. 扩展

如果划分还考虑顺序（1+2+1 和 1+1+2 算不同），问题就变成”组合”了，解法反而更简单，总数就是 2^(n-1)。这个结论当时挺反直觉，后来想想其实就是把 n 个”1”排成一排，在 n-1 个空档里决定切不切，才明白过来。