1180 放苹果
大约 4 分钟
1180 放苹果
【算法】 递推
【C++】 二维数组、递归、多组输入
【难度】 普及−
一、题目简述
把 个相同的苹果放入 个相同的盘子中,允许空盘。问有多少种不同的分法?
- "相同"意味着只关心数量分配,不关心哪个苹果在哪个盘子
- 盘子也一样,所以 和 算同一种分法
- 多组测试数据,,
示例:,输出 。
二、解题思路
2.1 问题分析
设 表示 个苹果放入 个盘子的方案数。关键在于分类讨论。
考虑盘子中是否有空盘,把问题分成互不重叠的两类:
- 有盘子空着 → (拿掉一个空盘,问题缩小)
- 没有盘子空着 → (每个盘子先放一个苹果占位,剩下的苹果再随意分)
2.2 递推公式
分两种情况:
情况一:(苹果比盘子少)
盘子里空的比苹果还多,那多出来的盘子一定是全空的。把满的盘子挑出来,空的去掉:
情况二:(苹果不少于盘子)
这是核心分类,两类不重不漏:
| 分类 | 含义 | 递推 |
|---|---|---|
| 至少有一个空盘 | 把那个空盘拿掉,问题变成 个苹果放进 个盘子 | |
| 没空盘 | 每个盘子先放 1 个苹果(共减 个),剩下的 个苹果继续分 |
边界条件:
| 条件 | 值 | 解释 |
|---|---|---|
| 0 个苹果,所有盘子都空,1 种方案 | ||
| () | 有苹果没盘子,0 种方案 |
2.3 手动模拟
用递推树追踪:
f(7,3) = f(7,2) + f(4,3) ← 7≥3, 拆成有空盘 + 没空盘
│ │
▼ ▼
f(7,2) f(4,3)
= f(7,1) = f(4,2) + f(1,3) ← 4≥3
+ f(5,2) │ │
│ │ ▼ ▼
▼ ▼ f(4,2) f(1,3)
f(7,1) f(5,2) = f(4,1) = f(1,1) = 1
= 1 = f(5,1) + f(2,2)
+ f(3,2) │ │
│ │ ▼ ▼
▼ ▼ f(4,1) f(2,2)
f(5,1) f(3,2) =1 = f(2,1)+f(0,2)
= 1 = f(3,1) = 1 + 1 = 2
+ f(1,2)
= 1 + 1 = 2逐步回代:
| 计算 | 值 | |
|---|---|---|
| 1 | ||
| 1 | ||
| 1+1=2 | ||
| 1+2=3 | ||
| 1+3=4 | ||
| 1+1=2 | ||
| 1+2=3 | ||
| 3+1=4 | ||
| 4+4=8 |
结果 ,与样例一致。✓
2.4 算法选择
,数据极小,递推(带记忆化的递归)即可。用二维数组 f[15][15] 存下所有可能状态,填表后每组数据 查询。
三、参考代码
#include <bits/stdc++.h>
using namespace std;
int f[15][15]; // f[m][n]: m 个苹果放入 n 个盘子
// 记忆化递归
int dfs(int m, int n) {
if (m == 0) return 1; // 0 个苹果,只有 1 种放法
if (n == 0) return 0; // 有苹果没盘子,0 种
if (f[m][n] != -1) return f[m][n]; // 已算过,直接返回
if (m < n)
f[m][n] = dfs(m, m); // 苹果比盘子少,多出来的盘子全空
else
f[m][n] = dfs(m, n - 1) + dfs(m - n, n); // 有空盘 + 没空盘
return f[m][n];
}
int main() {
// 初始化为 -1,表示未计算
memset(f, -1, sizeof(f));
int t;
cin >> t;
while (t--) {
int m, n;
cin >> m >> n;
cout << dfs(m, n) << endl;
}
return 0;
}另一种写法(DP 填表)
因为数据小,也可以直接递推打表:
#include <bits/stdc++.h>
using namespace std;
int f[15][15];
int main() {
// 边界:0 个苹果 → 1 种方案(全空)
for (int j = 0; j <= 10; j++) f[0][j] = 1;
for (int i = 1; i <= 10; i++) {
for (int j = 1; j <= 10; j++) {
if (i < j)
f[i][j] = f[i][i];
else
f[i][j] = f[i][j - 1] + f[i - j][j];
}
}
int t;
cin >> t;
while (t--) {
int m, n;
cin >> m >> n;
cout << f[m][n] << endl;
}
return 0;
}四、复杂度分析
- 时间复杂度:预处理 ,每组数据 查询。此处 ,瞬间完成。
- 空间复杂度:,用于存储递推表。
五、思维拓展
本题是经典的整数划分变体。类似模型:
| 变体 | 条件变化 |
|---|---|
| 整数划分 | 把 拆成不超过 个正整数的和 |
| 本题 | 等价于"把 拆成不超过 个正整数的和",允许零项 |
| 盘子有编号 | 用插板法(组合数), |
理解这道题的"有空盘 + 没空盘"二分法,对后续学习 DP 中的分类讨论思想很有帮助。
六、易错点
- 边界 :0 个苹果放 n 个盘子,只有全空 1 种方案,不是 0。
- 时别忘了走 :多出来的盘子一定空,直接裁剪。
- 递归记得记忆化:虽然 小,但不记忆化会大量重复计算。
- 多组输入:每次都要输出答案,注意
while (t--)的写法。
