A7978.放苹果 递归题解

$\color{red}{递归逻辑如下：}$

$\color{blue}{1.}$ 如果没有苹果了或者没有盘子了，没有分法，直接return 0;
$\color{blue}{2.}$ 如果只有一个盘子或只有一个苹果，只有一种分法(因为不考虑顺序)，return 1;
$\color{blue}{3.}$ 如果盘子数量为 $2$ ，则放法数量为 $m/n+1$ (此处为整除)(我研究的规律你们自己去试)
$\color{blue}{4.}$ 剩下的情况，如果 $m>n$ ，则有两种情况，空一个盘子不放，或每个盘子放一个苹果(若放完后的苹果数量比盘子数量少，盘子数量应减少)，return f(m,n-1)+f(m-n,min(m-n,n));
$\color{blue}{5.}$ 如果 $m==n$ ，也有两种情况，空一个盘子不放，或每个盘子放一个(这种情况苹果放完了，再递归下去还会return 0;没有意义，return f(m,n-1)+1;
$\color{blue}{6.}$ 如果 $m<n$ 不管怎么放至少有 $m-n$ 个盘子空着，只剩 $m$ 个盘子，所以return f(m,m);

C++ Code:

//递归的注释都在上面，这里就不用注释了吧
#include <bits/stdc++.h>
using namespace std;
int f(int m,int n){
    if (m==0&&n==0) return 0;
    if (m==1||n==1) return 1;
    if (n==2) return m/n+1;
    if (m>n) return f(m,n-1)+f(m-n,min(m-n,n));
    else if (m==n) return f(m,n-1)+1;
    else return f(m,m);
}
int main(){
    int t,m,n;
    cin>>t;
    while (t--){
        cin>>m>>n;
        cout<<f(m,min(m,n))<<endl;
    }
}