8227.放苹果

题目分析

把 M 个相同苹果放入 N 个相同盘子，允许空盘，求方案数。

关键点：苹果相同、盘子相同，只考虑数量的分配。

解题思路

用递归函数 f(m, n) 表示将 m 个苹果放入 n 个盘子的方案数：

递归边界：

• m == 0：没有苹果，只有 1 种方案（所有盘子为空）
• n == 1：只有 1 个盘子，只能放全部苹果，1 种方案
• m == 1：1 个苹果，无论多少个盘子，只有 1 种方案（放在某个盘子）

递归关系：

• 如果 m < n：至少有 n-m 个空盘，等价于 f(m, m)
• 如果 m >= n：
  • 有空盘：至少一个盘子为空，等价于 f(m, n-1)
  • 无空盘：每个盘子至少放 1 个，等价于 f(m-n, n)

代码实现

cpp
复制
1#include <iostream>
2using namespace std;
3
4int f(int m, int n) {
5    // 边界条件
6    if (m == 0 || n == 1 || m == 1) {
7        return 1;
8    }
9    // 苹果数小于盘子数，等价于苹果数等于盘子数
10    if (m < n) {
11        return f(m, m);
12    }
13    // 苹果数大于等于盘子数：有空盘 + 无空盘
14    return f(m, n - 1) + f(m - n, n);
15}
16
17int main() {
18    int T;
19    cin >> T;
20    
21    while (T--) {
22        int M, N;
23        cin >> M >> N;
24        cout << f(M, N) << endl;
25    }
26    
27    return 0;
28}

递归过程示例

以 f(7, 3) 为例：

f(7,3) = f(7,2) + f(4,3)
f(7,2) = f(7,1) + f(5,2) = 1 + (f(5,1) + f(3,2)) = 1 + 1 + (f(3,1) + f(1,2)) = 1 + 1 + 1 + 1 = 4
f(4,3) = f(4,2) + f(1,3) = (f(4,1) + f(2,2)) + 1 = 1 + (f(2,1) + f(0,2)) + 1 = 1 + 1 + 1 + 1 = 4
f(7,3) = 4 + 4 = 8

复杂度分析

• 时间复杂度：O(M×N)，但递归会重复计算
• 空间复杂度：O(N)，递归调用栈深度

优化建议（记忆化搜索）

cpp
复制
1#include <iostream>
2#include <cstring>
3using namespace std;
4
5int dp[15][15];
6
7int f(int m, int n) {
8    if (m == 0 || n == 1 || m == 1) return 1;
9    if (dp[m][n] != -1) return dp[m][n];
10    
11    if (m < n) {
12        dp[m][n] = f(m, m);
13    } else {
14        dp[m][n] = f(m, n - 1) + f(m - n, n);
15    }
16    return dp[m][n];
17}
18
19int main() {
20    int T;
21    cin >> T;
22    memset(dp, -1, sizeof(dp));
23    
24    while (T--) {
25        int M, N;
26        cin >> M >> N;
27        cout << f(M, N) << endl;
28    }
29    
30    return 0;
31}

测试验证

对于样例 7 3：

• 输出：8 ✓

其他测试：

• 3 5 → 3
• 4 4 → 5
• 0 5 → 1

核心要点

1. 递归边界要准确：m=0, n=1, m=1 都返回 1
2. 递归公式：f(m,n) = f(m,n-1) + f(m-n,n)（当 m≥n 时）
3. 苹果数小于盘子数时简化：f(m,n) = f(m,m)