题解 | #放苹果#

#include <iostream>

using namespace std;

int dp[11][11];

/**
 * 递归
 * m为0,一种；m为1两种；n为0一种；n为1两种
 */
int fio(int m,int n){
    if (m<=1 || n<=1) return 1;
    if (m<n) return fio(m,m);
    return fio(m,n-1) + fio(m-n,n);
}

/**
 * 动态规划
 * 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放
 * dp[i][j]表示把i个苹果放到j个盘子的放法
 * dp[0][j] = 1,dp[i][0] = 1
 */
int apple(int m,int n){
    for (int i = 0; i <= m; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (i<=1 || j==1) dp[i][j] = 1;
            else if (i<j) dp[i][j] = dp[i][i];
            else dp[i][j] = dp[i][j-1] + dp[i-j][j];
        }
    }
    return dp[m][n];
}

int main(){
    int m,n;
    while (cin>>m>>n){
        cout<<apple(m,n)<<endl;
    }
    return 0;
}