盘子相同就按非增序列去重,答案即 M 拆成不超过 N 个部分的拆分数;按「是否有空盘」分类递推打表,每组询问 O(1)。
OJ: roj
题目 ID: 1222
难度:普及-
标签:递推整数划分动态规划递归python
创建: 2026-10-07 15:23
更新: 2026-10-07 15:23
形式化题目
给定
由于盘子相同,
其中
即把
输入为
正解
思路
朴素做法。 逐盘决定苹果数,并强制"后面的盘不多于前面的盘":
dfs(当前盘下标, 上一盘苹果数, 剩余苹果数),走到最后一盘时若剩余苹果数不超过上一盘就记一种方案。
这条强制去重正是题目里"盘子相同"的那句话——它一次性排除了所有重排:
比如
这个搜法对本题规模(
关键观察:按"有没有空盘"给分法分类。 记
| 类别 | 特征 | 与哪个子问题一一对应 |
|---|---|---|
| 至少一个空盘 | 至少有一个 |
把 |
| 每个盘都非空 | 所有 |
每盘先各放 |
两类互不相交又覆盖全部方案,两边的对应关系都是双射(删掉一个空盘 / 每盘各减
这就是整数分拆的经典递推。它每算一个
边界。 几个退化情况必须单独定死,否则递推没有终点:
:苹果已经放完,剩下的盘子只能全空着,这算一种分法(0 个苹果时 全为 0); ( ):一个盘子都没有,苹果无处可放; - 当
时不必让递推下降到 :已经"每盘非空"的支路会算出 这种负数下标, 而事实上盘子多于苹果时,多出来的 个盘子必然空着, 这些格子在非增序列里就是末尾的一串 ,所以
加上这一条,
状态数决定写法。 状态只有
- Python 版用
functools.cache记忆化递归,天然只算到用得到的那些状态; - C++ 版直接从小到大递推填
dp[m][n]二维表,之后每组询问是一次数组取值。
下面用样例
flowchart TD R["f(7,3) = 8"] --> A["至少一个空盘:f(7,2) = 4"] R --> B["每盘都非空:f(4,3) = 4"] A --> A1["(7) (6,1) (5,2) (4,3)"] B --> B1["(5,1,1) (4,2,1) (3,3,1) (3,2,2)"]
读这张图要抓住两点。第一,左支的 4 种里都至少有一个
下表是
| 0 | 1 | 2 | 3 | |
|---|---|---|---|---|
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 2 | 0 | 1 | 2 | 2 |
| 3 | 0 | 1 | 2 | 3 |
| 4 | 0 | 1 | 3 | 4 |
| 5 | 0 | 1 | 3 | 5 |
| 6 | 0 | 1 | 4 | 7 |
| 7 | 0 | 1 | 4 | 8 |
三点观察:
代码
Python 版:
#!/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-07 15:14
# update_at: 2026-10-07 15:14
import sys
from functools import cache
@cache
def ways(m: int, n: int) -> int:
"""把 m 个相同苹果放进 n 个相同盘子(允许空盘)的分法数。"""
if m == 0:
return 1 # 苹果已放完,剩下的盘子只能空着
if n == 0:
return 0 # 没有盘子,剩下的苹果无处可放
if n > m:
return ways(m, m) # 盘子多于苹果,多出来的盘子必然空着
return ways(m, n - 1) + ways(m - n, n) # 至少一个空盘 + 每盘先放一个再分剩下的
def solve() -> None:
data = iter(map(int, sys.stdin.buffer.read().split()))
t = next(data, 0) # 测试数据组数;空输入按 0 组处理
out: list[str] = []
for _ in range(t):
m, n = next(data), next(data) # 本组询问的两个量
out.append(str(ways(m, n)))
if out: # t = 0 时题目要求输出为空,不能多一个换行
print('\n'.join(out))
if __name__ == "__main__":
solve()C++ 版(同一算法):
/**
* 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-07 15:14
* update_at: 2026-10-07 15:14
*/
// main.cpp:放苹果。把 M 个相同苹果放进 N 个相同盘子(允许空盘)的分法数,
// 就是「M 拆成不超过 N 个正整数之和」的拆分数,用整数分拆的递推式一次打表,每组询问 O(1)。
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXM = 10; // 题面 M 的上限
const int MAXN = 10; // 题面 N 的上限
// dp[m][n]:把 m 个相同苹果放进 n 个相同盘子、允许空盘的分法数,
// 即 m 的不超过 n 个部分的拆分数。答案最大是 dp[10][10] = 42。
ll dp[MAXM + 1][MAXN + 1];
// 按 m 从小到大、m 相同时按 n 从小到大打表
void build_table() {
for (int n = 0; n <= MAXN; n++) dp[0][n] = 1; // 0 个苹果:全是空盘,唯一分法
for (int m = 1; m <= MAXM; m++) {
dp[m][0] = 0; // 一个盘子都没有,非零个苹果放不下
for (int n = 1; n <= MAXN; n++) {
if (n > m) {
dp[m][n] = dp[m][m]; // 盘子比苹果多,多出来的盘子必然空着,可以砍掉
} else {
// 至少一个空盘:dp[m][n-1];每盘都非空:先各放 1 个,剩下 m-n 个任意放
dp[m][n] = dp[m][n - 1] + dp[m - n][n];
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
build_table();
ll t;
if (!(cin >> t)) return 0; // 无输入时直接结束
while (t-- > 0) {
ll m, n;
cin >> m >> n;
cout << dp[m][n] << "\n";
}
return 0;
}复杂度
- 时间:预处理填满
的表,每个状态 ,所以是 (本题 次加法); 之后每组询问 。总计 。Python 版用 cache记忆化, 只会展开实际被询问的状态,上界同样是。 - 空间:
的状态表(本题 个整数),无递归以外的额外开销; Python 记忆化递归深度上界 。 - 实测:C++ 编译后 10 个测试点单点
s / 峰值 8.4 MB, Python 单点 s / 峰值 14.6 MB(限时 1000 ms / 64 MB), 两种实现在 10 个测试点上逐字节输出一致。
总结
- "盘子相同"就是去重约定:它把分法与"非增序列"一一对应,于是题目从"放球"变成了整数分拆;
如果盘子是不同的,答案会变成隔板法组合数
, 就该是 而不是 。 - 分类的依据要能反向还原:按"至少一个空盘 / 每盘非空"分,两类都能由子问题可逆地构造出来
(删空盘、每盘减
),所以既能相加也不会重复计数,这是本题唯一的推导步骤。 - 边界定死两头:
、 ,再加上 的剪枝,递推就能稳稳落地;少了任何一条都会出现负数下标或漏算空盘方案。 - 范围小就别硬套技巧:状态只有
个且都很小,直接打表 + 每组 查询是最清楚的写法; Python 侧用 cache记忆化就能达到同样的复杂度。 - 读入细节:
是题面允许的合法输入,此时不能输出任何字符(连换行都不能多), 代码里用 if out:守住这一条。