P4742 苹果摆放（提高）

解题思路

题目说：把 M 个同样的苹果放进 N 个同样的盘子里，允许有的盘子空着，问有多少种不同的分法。注意 5,1,1 和 1,5,1 是同一种分法，也就是说我们只关心每个盘子里有几个苹果，不关心是哪个盘子。

设函数 f(m,n) 表示把 m 个苹果放进 n 个盘子的分法数。分几种情况：

1. 如果 m=0，一个苹果都没有，所有盘子都空着，只有 1 种分法；
2. 如果 n=1，只有一个盘子，所有苹果都放这个盘子里，只有 1 种分法；
3. 如果 m<n，盘子比苹果多，那么多出来的空盘子没有任何作用，等价于把 m 个苹果放进 m 个盘子，即 f(m,n)=f(m,m)；
4. 其余情况，可以分成两大类：第一类是"有空盘子"，那至少空了一个盘子，分法数是 f(m,n-1)；第二类是"每个盘子都不空"，那先给每个盘子放 1 个苹果，剩 m-n 个苹果再随便放，分法数是 f(m-n,n)。所以 f(m,n)=f(m,n-1)+f(m-n,n)。

用例子验证：M=7,N=3。f(7,3)=f(7,2)+f(4,3)=4+4=8，和样例输出一致。

边界情况：M、N 最小是 1，最大是 10，递归的层数不会很深，直接递归就能算出来。每组数据分别算一遍即可。

参考代码

// 苹果摆放：递归求M个苹果放N个盘子的分法数
#include <iostream>

int put(int m, int n) {
    if (m == 0 || n == 1) return 1;        // 没苹果或只有1个盘子
    if (m < n) return put(m, m);           // 盘子比苹果多，等价于m个盘子
    return put(m - n, n) + put(m, n - 1);  // 有空盘 + 每个盘至少1个
}

int main() {
    int t;
    std::cin >> t;
    while (t--) {
        int m, n;
        std::cin >> m >> n;
        std::cout << put(m, n) << "\n";
    }
    return 0;
}

复杂度分析

递归的状态是 (m,n)，其中 0≤m≤10、1≤n≤10，最多有 11×10=110 个不同的状态。每个状态只会往下调用两三个新状态，所以时间复杂度大约是 O(110)，几乎可以看成常数时间。空间上递归深度最多十几层，是 O(min(m,n))。t 最多 20 组数据，每组都瞬间出结果，速度非常快。