数的划分

题目描述

将整数 $n$ 分成 $k$ 份，每份不能为空，方案不考虑顺序。 $6 < n \le 200$ ， $2 \le k \le 6$ 。输入 $n,k$ ，输出不同分法的种数。样例 $7\ 3$ 输出 $4$ 。

思路

设 $p_k(n)$ 为把 $n$ 拆成 $k$ 个正整数且不计顺序的方案数。按最小值是否为 $1$ 分类：最小值是 $1$ 时去掉一个 $1$ ，得到 $p_{k-1}(n-1)$ ；最小值 $\ge 2$ 时每份减 $1$ ，得到 $p_k(n-k)$ 。于是 $p_k(n)=p_{k-1}(n-1)+p_k(n-k)$ ，边界 $n<k$ 为 $0$ 、 $k=1$ 为 $1$ 。记忆化搜索即可，状态数 $O(nk)$ 。

参考代码

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
31
32#!/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 04:40
# update_at: 2026-10-02 04:40

import sys
from functools import cache


@cache
def ways(n: int, k: int) -> int:
    """把 n 分成 k 份非空、不计顺序的正整数方案数（约定每份从小到大）。"""
    if n < k:  # 每份至少 1，k 份最少也要 k
        return 0
    if k == 1:  # 只剩一份，唯一分法就是 n 本身
        return 1
    # 按"是否存在等于 1 的一份"分类：
    # 有：去掉这份 1，变成 ways(n-1, k-1)；
    # 没有：每份都 ≥2，每份先扣掉 1，变成 ways(n-k, k)。
    return ways(n - 1, k - 1) + ways(n - k, k)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n, k = next(data), next(data)
    print(ways(n, k))


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/**
 * 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 12:31
 * update_at: 2026-10-06 12:31
 */
#include <cstdio>
#include <cstring>
using namespace std;

typedef long long ll;

ll n, k;
ll memo[205][7]; // memo[i][j] 表示把 i 分成 j 份的方案数

// 把 total 分成 parts 份非空、不计顺序的正整数方案数
ll ways(ll total, ll parts) {
    if (total < parts) return 0; // 每份至少 1，总和小于份数则无解
    if (parts == 1) return 1;    // 只剩一份，唯一分法就是 total 本身
    if (memo[total][parts] != -1) return memo[total][parts];
    // 按是否有一份等于 1 分类：有则去掉一个 1；没有则每份先减 1
    memo[total][parts] = ways(total - 1, parts - 1) + ways(total - parts, parts);
    return memo[total][parts];
}

int main() {
    memset(memo, -1, sizeof(memo));
    scanf("%lld %lld", &n, &k);
    printf("%lld\n", ways(n, k));
    return 0;
}

目录

题目描述

思路

参考代码