题解 | #放苹果#

#include<bits/stdc++.h>
using namespace std;
// //方法一：DFS
// int push_apple(int m,int n)
// {
//     if(m==0) return 1;//零个苹果，方法一种
//     if(n==0) return 0;//零个盘子，方法零种
//     if(m<n) return push_apple(m,m);//苹果少于盘子，n-m个盘子没用
//     else return push_apple(m,n-1)+push_apple(m-n,n);//只有两种可能，要么至少有一个盘子为空push_apple(m,n-1)，要么每个盘子都至少有一个苹果push_apple(m-n,n)
// }
// int main()
// {
//     int m,n;
//     while(cin>>m>>n)
//     {
//         cout<<push_apple(m,n);//m个苹果放进n个盘子
//     }
// }
//方法二：动态规划
int main()
{
    int m,n;
    while(cin>>m>>n)
    {
        int dp[m+1][n+1];//dp[i][j]代表i+1个苹果放进j+1个盘子的分法
        //dp初始化
        for(int i=0;i<=m;i++)
        {
            for(int j=0;j<=n;j++)
            {
                dp[i][j]=0;
            }
        }
        //如果苹果是零个，无论盘子几个，方法都只有一个，那就是每个盘子都不装
        for(int i=0;i<=n;i++) dp[0][i]=1;
        for(int i=1;i<=m;i++)
        {
            for(int j=1;j<=n;j++)
            {
                //苹果少于盘子，n-m个盘子没用
                if(i<j) dp[i][j]=dp[i][i];
                //否则。只有两种可能，要么至少有一个盘子为空push_apple(m,n-1)，要么每个盘子都至少有一个苹果push_apple(m-n,n)
                else dp[i][j]=dp[i][j-1]+dp[i-j][j];
            }
        }
        cout<<dp[m][n]<<endl;
    }
}