题解 | #放苹果#

#include<stdio.h>
#include<string.h>

// 方法1 递归
// int put_apple(int m,int n){
//     if(m==0 || n==1)  // n=1对应n会减少的出口条件;m==0对应m会减少的条件
//         return 1;     // 例子：f(2,2) = f(2,1)+f(0,2),f(2,2) = 2,f(2,1)=1,所以f(0,2)=1;
//     if(n>m)
//         return put_apple(m,m);
//     else
//         return put_apple(m,n-1)+put_apple(m-n,n);
// }

int main(){
    int m,n;
    // 方法1 递归
//     while(scanf("%d %d",&m,&n)!=EOF)  // 防止多组输入 建议使用while
//     {
//         int num = put_apple(m,n);
//         printf("%d",num);
//     }
    
    // 方法2 动态规划
    while(scanf("%d %d",&m,&n)!=EOF){
        int dp[11][10]; // 11 对应苹果数种类  10对应盘子种类
        //初始化
        for(int i=0;i<11;i++){
            if(i<10){
                dp[0][i] = 1;
                dp[1][i] = 1;
            }
            dp[i][1] = 1;   
        }
        for(int i = 1;i<=m;i++){
            for(int j=2;j<=n;j++){ // j从2开始是因为不会出现0个盘子
                if(j>i)
                    dp[i][j] = dp[i][i];
                else
                    dp[i][j] = dp[i][j-1]+dp[i-j][j];
            }
        }
        printf("%d",dp[m][n]);
    }
}