放苹果

题目描述

把 $M$ 个同样的苹果放进 $N$ 个同样的盘子里，允许有的盘子空着，求不同的分法数 $K$ ； $5,1,1$ 与 $1,5,1$ 是同一种分法。输入：第一行是测试数据数目 $t$ （ $0 \leqslant t \leqslant 20$ ），以下每行两个整数 $M$ 和 $N$ ，以空格分开（ $1 \leqslant M, N \leqslant 10$ ）。输出：对每组数据一行输出相应的 $K$ 。样例输入 1 与 7 3 对应输出 8。

思路

设 $f(m,n)$ 为 $m$ 个苹果放进 $n$ 个盘子的分法数，按最后一个盘子是否为空不重不漏地分两类：空则少一个盘子得 $f(m,n-1)$ ；非空则非降序下所有盘子都非空，每盘先垫一个苹果得 $f(m-n,n)$ 。故 $f(m,n)=f(m,n-1)+f(m-n,n)$ ，边界 $f(0,n)=f(m,1)=1$ ， $m<n$ 时多余盘子必然空着可折叠为 $f(m,m)$ ，记忆化递推即可。

参考代码

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
33
34
35
36
37
38
39#!/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-07-05 22:10
# update_at: 2026-07-05 22:10

import sys
from functools import cache


@cache
def count(m: int, n: int) -> int:
    """m 个同样的苹果放进 n 个同样的盘子（允许空盘）的方案数。

    边界：没有苹果、或只剩一个盘子，都只有一种放法。
    """
    if m == 0 or n == 1:
        return 1
    if m < n:
        return count(m, m)  # 盘子比苹果多，多出的盘子必然空着，与 m 个盘子等价
    # 按第 n 个盘子是否为空分类：空 → 少一个盘子；不空 → 每盘先垫 1 个
    return count(m, n - 1) + count(m - n, n)


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

    out: list[str] = []
    for _ in range(T):
        m, n = next(data), next(data)  # 苹果数 m，盘子数 n
        out.append(str(count(m, n)))

    print('\n'.join(out))


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/**
 * 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:11
 * update_at: 2026-10-05 05:11
 */

#include <cstdio>

typedef long long ll;

ll memo[15][15]; // memo[m][n] = m 个苹果放进 n 个盘子的分法数，-1 表示还没算过

// 求把 m 个同样的苹果放进 n 个同样的盘子（允许空盘）的分法数
ll count_ways(ll m, ll n) {
    if (memo[m][n] != -1) return memo[m][n]; // 记忆化：每个状态只算一次
    ll res;
    if (m == 0 || n == 1) {
        res = 1; // 没有苹果（全空）或只剩一个盘子，都只有一种放法
    } else if (m < n) {
        res = count_ways(m, m); // 盘子比苹果多，多出的盘子必然空着，与 m 个盘子等价
    } else {
        // 按第 n 个盘子是否为空分类，两类互斥且不漏：
        // 空   -> 少一个盘子：count_ways(m, n-1)
        // 非空 -> 非降序下所有盘子都非空，每盘先垫 1 个苹果：count_ways(m-n, n)
        res = count_ways(m, n - 1) + count_ways(m - n, n);
    }
    memo[m][n] = res;
    return res;
}

int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        ll m, n;
        scanf("%lld %lld", &m, &n);
        // 多组数据共用一张记忆化表：先把会用到的范围清成 -1
        for (ll i = 0; i <= m; ++i)
            for (ll j = 1; j <= n; ++j)
                memo[i][j] = -1;
        printf("%lld\n", count_ways(m, n));
    }
    return 0;
}

目录

题目描述

思路

参考代码