整数划分

题目描述

给定正整数 $n$ ，求把 $n$ 写成若干正整数之和的方案数（加数顺序不同视为同一划分， $n$ 本身也算一种），即划分数 $p(n)$ 。

思路

完全背包计数：令 $dp[j]$ 为凑出 $j$ 的划分数，枚举每个可用加数 $i=1\dots n$ 做 $dp[j] \mathrel{+}= dp[j-i]$ ，恰好消除顺序重复， $O(n^2)$ 得 $p(n)$ 。

参考代码

Python 版：

python

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
27
28
29
30#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 15:22
# update_at: 2026-10-02 15:22

import sys
from functools import cache


@cache
def parts(rest: int, cap: int) -> int:
    """把 rest 拆成若干不超过 cap 的正整数之和（顺序无关）的方案数。

    枚举首段 x，再把 rest-x 交给同一个问题、上限收紧为 x：
    下一段永远不超过上一段，5+1 与 1+5 落进同一条分支，天然不重不漏。
    """
    if rest == 0:
        return 1  # 空拆分：各段恰好拼完，算一种方案
    return sum(parts(rest - x, x) for x in range(min(rest, cap), 0, -1))


def solve() -> None:
    n = int(sys.stdin.buffer.read())
    print(parts(n, n))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-06 16:30
 * update_at: 2026-10-06 16:30
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1005; // 题目测试数据 n 不大，状态表开到 1000 足够

// memo[r][c] 表示把 r 拆成若干不超过 c 的正整数之和的方案数；-1 表示未计算
ll memo[MAXN][MAXN];

// parts(r, c)：把 r 拆成若干不超过 c 的正整数之和的方案数
ll parts(int r, int c) {
    if (r == 0) return 1; // 已经拼完，空拆分算一种
    if (c <= 0) return 0; // 还有剩余但上限为 0，无法拆分
    ll &res = memo[r][c];
    if (res != -1) return res;
    res = 0;
    int up = min(r, c);
    for (int x = 1; x <= up; x++) {
        // 首段取 x，下一段上限收紧为 x
        res += parts(r - x, x);
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    if (!(cin >> n)) return 0;

    // 只清理实际需要使用的状态范围
    for (int i = 0; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            memo[i][j] = -1;
        }
    }

    cout << parts(n, n) << "\n";
    return 0;
}

目录

题目描述

思路

参考代码