放苹果

题目描述

把 $M$ 个同样的苹果放进 $N$ 个同样的盘子，允许有的盘子空着。盘子无编号，如 5 1 1 与 1 5 1 算同一种。给定 $t$ 组 $M, N$ （ $1 \leqslant M, N \leqslant 10$ ），每组输出不同分法数 $K$ 。

思路

设 $f(m,n)$ 为 $m$ 个苹果放进 $n$ 个相同盘子（可空）的分法数。按“有没有空盘”分类：有空盘时去掉一个空盘，得 $f(m,n-1)$ ；无空盘时每盘先减一个，得 $f(m-n,n)$ 。边界 $f(0,n)=1$ ， $f(m,0)=0$ （ $m>0$ ），并用记忆化把重复子问题只算一次。

参考代码

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-09-29 23:27
# update_at: 2026-09-29 23:27

import sys
from functools import cache


@cache
def ways(apples: int, plates: int) -> int:
    """m 个苹果放进 n 个相同盘子（可空）的分法数，按"有没有空盘"分类。"""
    if apples == 0:
        return 1  # 苹果放完：所有盘子都空着，只有一种分法
    if plates == 0:
        return 0  # 苹果没放完却没盘子了，无解
    if plates > apples:
        return ways(apples, apples)  # 多余盘子必空，等价于只用 m 个盘子
    # 不用第 n 个盘子 ways(m, n-1)；第 n 个盘子至少放一个，先扣掉再递归
    return ways(apples, plates - 1) + ways(apples - plates, plates)


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    t = next(data)  # 询问组数
    print('\n'.join(str(ways(next(data), next(data))) for _ in range(t)))


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/**
 * 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 05:32
 * update_at: 2026-10-05 05:33
 */
#include <cstdio>
#include <cstring>

typedef long long ll;

const int MAXM = 10;
const int MAXN = 10;

// memo[m][n]：m 个苹果放进 n 个相同盘子（可空）的分法数，-1 表示未计算
ll memo[MAXM + 1][MAXN + 1];

// m 个苹果放进 n 个相同盘子（可空）的分法数
ll ways(int m, int n) {
    if (m == 0) return 1;          // 苹果放完，所有盘子空着，只有一种分法
    if (n == 0) return 0;          // 苹果没放完却没盘子了，无解
    ll &res = memo[m][n];
    if (res != -1) return res;
    if (n > m) return res = ways(m, m); // 多余盘子必空，等价于只用 m 个盘子
    // 有空盘：不用第 n 个盘子；无空盘：每盘先放一个，再递归
    return res = ways(m, n - 1) + ways(m - n, n);
}

int main() {
    memset(memo, -1, sizeof(memo)); // 初始化记忆化表
    int t;
    scanf("%d", &t);
    while (t--) {
        int m, n;
        scanf("%d %d", &m, &n);
        printf("%lld\n", ways(m, n));
    }
    return 0;
}

目录

题目描述

思路

参考代码