形式化题目

给定正整数 $n$ 和 $k$（$1 \leqslant n \leqslant 200$，$1 \leqslant k \leqslant 7$）。 求将 $n$ 拆分成 $k$ 个正整数之和的无序划分方案数，即满足以下条件的正整数序列 $(x_1, x_2, \dots, x_k)$ 的不同集合数目：

动态规划 / 记忆化搜索

思路

为了避免排列顺序对计数产生干扰（例如 $\{1, 1, 5\}$ 与 $\{1, 5, 1\}$ 重复），我们可以假定拆分出的序列满足单调不降：$1 \leqslant x_1 \leqslant x_2 \leqslant \cdots \leqslant x_k$。

对于任意一种满足条件的拆分，观察其最小元素 $x_1$ 的取值：

1. 最小项为 $1$（即 $x_1 = 1$）： 此时拆分中至少包含一个 $1$。如果拿掉这个 $1$，剩下 $k-1$ 个数的和为 $n - 1$。这等价于将整数 $n - 1$ 拆分成 $k - 1$ 份正整数。
2. 最小项大于 $1$（即 $x_1 \geqslant 2$）： 此时所有分出的数都大于等于 $2$。如果我们给每一份都减去 $1$（共减去 $k$），则每一份仍为正整数（$x_i - 1 \geqslant 1$），且它们的和变为 $n - k$。这与将整数 $n - k$ 拆分成 $k$ 份正整数完全一一对应。

上述两类拆分互斥且覆盖了所有合法划分，根据加法原理，设 $f(n, k)$ 为划分方案数，可得状态转移方程：

边界条件：

• 若 $n < k$ 或 $k \leqslant 0$，无法拆分成 $k$ 份正整数，方案数为 $0$；
• 若 $n = k$ 或 $k = 1$，方案唯一（全为 $1$ 或整除自身），方案数为 $1$。

样例推导表格 ($n=7, k=3$)

状态转移计算过程如下表所示：

代码

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
31
32
33
34
35#!/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-03-31 10:00
# update_at: 2026-03-31 10:00

import sys
from functools import cache


@cache
def count_partitions(remain: int, parts: int) -> int:
    """求将整数 remain 划分为 parts 份正整数的方案数。"""
    if remain < parts or parts <= 0:
        return 0
    if remain == parts or parts == 1:
        return 1
    # 状态转移：若划分包含 1，对应 count_partitions(remain - 1, parts - 1)；
    # 若每份均大于 1，每份各减 1，对应 count_partitions(remain - parts, parts)。
    return count_partitions(remain - 1, parts - 1) + count_partitions(remain - parts, parts)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    try:
        n, k = next(data), next(data)
    except StopIteration:
        return
    ans = count_partitions(n, k)
    print(ans)


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

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/**
 * 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 01:38
 * update_at: 2026-10-06 01:38
 */
// main.cpp：数的划分，按题解主算法做二维 DP。
// f(n, k) 表示把 n 拆成 k 份正整数的无序方案数：
// 按拆分中最小项是否为 1 分类，可得 f(n, k) = f(n-1, k-1) + f(n-k, k)。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 205;
const int MAXK = 10;

ll f[MAXN][MAXK]; // f[n][k]：把 n 拆成 k 份正整数的方案数

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

    ll n, k;
    cin >> n >> k;

    // 边界：k = 1 时只有一种拆法（n 本身）；其余从 2 份开始递推。
    for (ll i = 1; i <= n; i++) f[i][1] = 1;

    // 递推：f[i][j] = f[i-1][j-1]（最小项为 1）+ f[i-j][j]（每份减 1 后仍为 j 份正整数）。
    for (ll i = 2; i <= n; i++) {
        for (ll j = 2; j <= k; j++) {
            if (i < j) continue; // 份数比和还大，无法拆分
            f[i][j] = f[i - 1][j - 1] + f[i - j][j];
        }
    }

    cout << f[n][k] << endl;

    return 0;
}

复杂度

• 时间复杂度：状态总数至多 $O(n k)$，每个状态的转移仅包含常数次加法，总时间复杂度为 $O(n k)$。对于 $n \leqslant 200, k \leqslant 7$，总操作次数在千次以内，运行时间 $< 20\text{ms}$。
• 空间复杂度：递归栈最大深度为 $O(n)$，记忆化哈希表状态容量为 $O(n k)$，占用空间几兆字节，远低于 $128\text{MB}$ 限制。

总结

本题是整数划分问题的经典模型。解决“无序划分”计数的突破口在于：

1. 有序化思维：按单调不降定序，使集合划分唯一映射到有序序列；
2. 两分策略：依据“最小值是否为 1”划分子问题，巧妙规避了枚举具体数值的循环，直接得出简洁优美的 $O(n k)$ 动态规划递推。