题解 | #放苹果#

#include<iostream>
using namespace std;
int f(int m, int n) {   //使用递归的方式 当只有一个盘子 或者没有苹果的时候函数返回一种结果（一个苹果的时候，即返回f（1，1）为1） 
    if ((m == 0) || (n == 1)) return 1;
    if (n > m) return f(m, m);
    else return f(m, n - 1) + f(m - n, n);
}//这个递归公式的核心思想是将问题分解为更小的子问题来解决。我们可以将将m个苹果放入n个盘子中的方案分为两类：一类是至少有一个盘子为空，另一类是每个盘子都至少有一个苹果。对于第一类方案，我们可以将问题转化为将m个苹果放入n-1个盘子中，因为至少有一个盘子是空的。因此，这一类方案的数量就是f(m,n-1)。对于第二类方案，我们可以先在每个盘子中放一个苹果，然后再考虑如何将剩下的m-n个苹果放入n个盘子中。这样，这一类方案的数量就是f(m-n,n)。


int main() {
    int m, n;
    while (cin >> m >> n) {
        cout << f(m, n) << endl;//迭代运算即可
    }
    return 0;
}