P1664. 放苹果 题解

题目分析

将 $M$ 个相同的苹果放入 $N$ 个相同的盘子中（允许空盘），求不同的分法总数。由于盘子无区别，分法的顺序不影响结果（如 $5,1,1$ 和 $1,5,1$ 视为同一种分法）。

递归思路

问题的核心是利用递归分解子问题，关键在于不考虑盘子顺序，通过以下两种情况覆盖所有分法：

1. 至少有一个空盘：此时问题等价于将 $M$ 个苹果放入 $N-1$ 个盘子中（多余的一个盘子空着）。
2. 所有盘子非空：此时先给每个盘子放 $1$ 个苹果（共放 $N$ 个），剩下的 $M-N$ 个苹果继续分给 $N$ 个盘子（允许盘子再次空着）。

递归终止条件

• 当 $M=0$（无苹果）：所有盘子必须空着，仅 $1$ 种分法。
• 当 $N=1$（仅1个盘子）：所有苹果必须放入该盘子，仅 $1$ 种分法。
• 当 $M < N$（苹果数少于盘子数）：多余的盘子必然空着，等价于用 $M$ 个盘子放 $M$ 个苹果（即 $\text{count}(M, M)$）。

复杂度分析

• 时间复杂度：递归深度为 $O(\min(M, N))$，每个递归节点产生两个子问题，总时间复杂度为 $O(2^{\min(M,N)})$。由于题目中 $M, N \leq 10$，该复杂度完全可接受。
• 空间复杂度：递归栈的最大深度为 $O(\min(M, N))$，空间复杂度为 $O(\min(M, N))$。

标程

#include <stdio.h> 

// 递归函数：计算m个苹果放入n个盘子的分法数
int count(int x, int y) { 
    if (y == 1 || x == 0)  // 终止条件：1个盘子或0个苹果
        return 1; 
    if (x < y)  // 苹果数 < 盘子数，多余盘子必空，等价于用x个盘子
        return count(x, x); 
    // 两种情况之和：至少1个空盘 + 所有盘子非空
    return count(x, y - 1) + count(x - y, y); 
} 

int main() { 
    int t, m, n; 
    scanf("%d", &t);  // 读取测试用例数
    for (int i = 0; i < t; i++) { 
        scanf("%d%d", &m, &n);  // 读取每组m（苹果数）和n（盘子数）
        printf("%d\n", count(m, n));  // 输出分法数
    } 
    return 0; 
}

该代码通过递归巧妙分解子问题，覆盖所有可能的分法，正确解决了“放苹果”问题。