「一本通 1.3 例 1」数的划分

题目描述

给定两个整数 $n, k$ ，把 $n$ 拆成恰好 $k$ 个正整数之和，同一种拆法改变顺序只算一次。

例如 $n=7, k=3$ 时答案为 $4$ ： $1,1,5$ ； $1,2,4$ ； $1,3,3$ ； $2,2,3$ 。

思路

为避免重复，约定每份按不减顺序排列。设 $f[i][j]$ 表示把 $i$ 拆成 $j$ 个不减正整数之和的方案数：末份为 $1$ 时去掉它，对应 $f[i-1][j-1]$ ；末份至少为 $2$ 时每份都减 $1$ ，对应 $f[i-j][j]$ 。转移方程为 $f[i][j] = f[i-1][j-1] + f[i-j][j]$ ，答案即 $f[n][k]$ 。

参考代码

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# 「一本通 1.3 例 1」数的划分：把 n 分成 k 个互不相同考虑顺序的方案数（不减划分）
# f[i][j]：把 i 分成 j 份（每份 >= 1，不减排列）的方案数
# 转移：f[i][j] = f[i-1][j-1]（第 j 份恰为 1，去掉它）+ f[i-j][j]（每份都减 1）
import sys
from functools import cache
from sys import setrecursionlimit

setrecursionlimit(100000)


@cache
def f(i: int, j: int) -> int:
    if i < j or j == 0:      # 份不够分或份数为 0
        return 0
    if j == 1:               # 只剩一份，全部给它
        return 1
    return f(i - 1, j - 1) + f(i - j, j)  # 递归展开为二维 DP


data = iter(map(int, sys.stdin.buffer.read().split()))
n = next(data)
k = next(data)
print(f(n, k))

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/**
 * 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-05 23:47
 * update_at: 2026-10-05 23:48
 */
#include <iostream>
using namespace std;

typedef long long ll;

const int MAXN = 205; // n 最大值
const int MAXK = 10;  // k 最大值

ll f[MAXN][MAXK]; // f[i][j]：把 i 分成 j 份（不减、每份≥1）的方案数

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

    int n, k;
    cin >> n >> k;

    // 边界：拆成 1 份只有 1 种；i < j 时不够分，保持 0
    for (int i = 1; i <= n; i++) f[i][1] = 1;

    for (int i = 1; i <= n; i++) {
        for (int j = 2; j <= k && j <= i; j++) {
            // 末份为 1：去掉它；末份≥2：每份减 1
            // 注意 i - j 可能为 0，f[0][*] 保持 0 即可
            f[i][j] = f[i - 1][j - 1] + f[i - j][j];
        }
    }

    cout << f[n][k] << '\n';
    return 0;
}

「一本通 1.3 例 1」数的划分

目录

题目描述

思路

参考代码