题解 | 放苹果

#include <bits/stdc++.h>
#include <cstring>
using namespace std;

int main(){
    int m,n;
    while(cin>>m>>n){
        int dp[21][21];
        memset(dp, 0, sizeof(dp));
        for(int i=0;i<=m;i++){
            for(int j=1;j<=n;j++){
                if(i==0||j==1)dp[i][j]=1;//无论如何都是1
                else if(i<j)dp[i][j]=dp[i][i];//由于相同的视为一个，所以盘子多的时候问题缩减
                else dp[i][j]=dp[i][j-1]+dp[i-j][j];//果子多的时候，有两种分法，有空盘，无空盘，二者出现问题缩减
            }
        }
        cout<<dp[m][n]<<endl;
    }
}

这个问题属于背包问题的抽象变化，最复杂的情况是果子大于盘子的时候，这时候可以分为两个类型，盘子用完，盘子没用完，对于没用完的情况，因为我们采用递归存储，存储的此类对象也是一个没用完和用完两种情况的，因此，没用完，我们取最小的情况，也就是只有一个没用完，对于多个没用完的，在这个内部的数值里，已经体现了。对于用完的，其实就缩减为果子更少，但是盘子还是这么多的情况。