题解 | #放苹果#C++递归一共18行代码

递归做多了就跟找规律一样。
先假设盘子>苹果，那一定有n-m个盘子空着，所以此时fun(m,n) = f(m,m)
当盘子<=苹果时，分成含0和不含0两种
含0：至少一个盘子空着f(m,n) = f(m,n-1)
不含0：所有盘子都有苹果，从每个盘子都拿掉一个苹果不会影响结果，此时f(m,n) = f(m-n,n)，但最后结果要算上这部分 所以f(m,n) = f(m,n-1)+f(m-n,n)

#include <iostream>
using namespace std;
int fun(int m, int n) {
    if(m==0 || n==1)
        return 1;
    if(n>m)
        return fun(m,m);
    else
        return fun(m,n-1)+fun(m-n,n);
}
int main()
{
    int m,n;
    while(cin>>m>>n)
    {
        cout<<fun(m,n)<<endl;;
    }
}