题解 | #放苹果#

//动态规划
#include "stdio.h"
int dp(int m,int n){
    if(n == 1)
        return 1;
    if(m == 0)
        return 1;
    if(m < n)
        return dp(m,m);//苹果数小于盘子数时，相当于盘子数减少到苹果数的次数（盘子多了，很多分法重复了）
    return dp(m,n-1)+dp(m-n,n);//n-1个盘子分m个苹果(至少有一个盘子为空)和
                                     // n个盘子分m个苹果(没有盘子为空),m-n为每个盘子先放一个
}

int main(){
    int m,n;//m为苹果数，n为盘子数
    while (scanf("%d%d",&m,&n)!=EOF){
        printf("%d\n", dp(m,n));
    }
}