题解 | #放苹果#

放苹果链接

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int main(){
    int m,n;
    while(cin>>m>>n){
        int dp[m+1][n+1];
        for(int i=0;i<m+1;i++){
            for(int j=0;j<n+1;j++){
                // 苹果数多于盘子数
                // 分解成有空盘子情况：预留一个盘子
                // 分解成无空盘子情况：每个盘子放一个苹果
                if(j==0) dp[i][j] = 0; // 盘子数为0，无解
                if(i==1||j==1||i==0) dp[i][j] = 1; //盘子数为1，苹果数为0，1都只有一种方法
                else if(i>=j)dp[i][j]= dp[i-j][j] + dp[i][j-1];
                // 盘子数多于苹果数
                // 必有i-j个空盘子 转化为求j-（j-i）=i个盘子放i个苹果
                else dp[i][j] = dp[i][i];
            }
        }
        cout<<dp[m][n]<<"\n";
    }
}