题目的主要信息：

• 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放
• 共有多少种不同的分法，不区分顺序

方法一：递归

具体做法：

因为不区分顺序，所以只考虑苹果分了几份，每份多少个，很容易知道当苹果为0个的时候或者盘子只有1个的时候，只有1种分法。那这个问题子问题就是苹果更少或者盘子更少的情况，因此可以用递归解决，上述只有一种分法的两个情况就是递归的出口。

我们再来看，当盘子数量大于苹果数量的时候，至少会有$n-mn-m$n−m个盘子必定是空的，分法只能在其他$mm$m个盘子中进行，因此它就等于它的子问题$mm$m个苹果$mm$m个盘子有多少种分法。

当苹果数量大于等于盘子数量时，可以分成两类：至少有一个盘子空着或者全部盘子都有苹果（这里相当于将苹果拿走盘子这么多个，剩余的分法才是重要的），而这两种情况之和就是苹果数量大于等于盘子数量的总分法。

#include<iostream>
using namespace std;

int recursion(int m, int n){
    if(m == 0 || n == 1) //如果没有苹果或者只剩下一个盘子，只有1种分法
        return 1;
    else if(m < n) //苹果数少于盘子数分法等于苹果数等于盘子数的分法，因为注定有n-m个盘子空
        return recursion(m, m);
    else //其他情况可以等于至少一个盘子空着加上全部盘子都有苹果
        return recursion(m, n - 1) + recursion(m - n, n);
}

int main(){
    int m, n;
    while(cin >> m >> n) //输入苹果数和盘子数
        cout << recursion(m, n) << endl; //递归解决
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(2^n\right)O(2^n)$O(2n)，树型递归，最大深度为$nn$n，总共递归$2^{n}2^n$2n次
• 空间复杂度：$O\left(n\right)O(n)$O(n)，递归栈最大深度不超过$nn$n

方法二：动态规划

具体做法：

递归是自顶向下搜索，然后自底向上相加，我们可以直接用自底向上相加。

用动态规划的方法，$dp\left[i\right]\left[j\right]dp[i][j]$dp[i][j]表示$ii$i个苹果分在$jj$j个盘子中的分法，首先苹果数为0即$i=0i=0$i=0全部初始化为1，然后遍历二维数组将dp数组填满，当$ii$i小于$jj$j的时候，苹果数少于盘子数，则等于它前一个盘子时的分法，因为这个盘子相当于常空着，没有用；当$ii$i大于等于$jj$j的时候，苹果数大于等于盘子数，则它等于上一个盘子的数量（即相当于至少有这个盘子是空的）加上苹果数减去盘子数且盘子数不变时的分法（即相当于每个盘子都有，排除这些后的分法）。

整体思路类似递归往上加。

#include<iostream>
#include<vector>
using namespace std;

int main(){
    int m, n;
    while(cin >> m >> n){
        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0)); //dp[i][j]表示i个苹果放在j个盘子的分法
        for(int i = 1; i <= n; i++)
            dp[0][i] = 1; //0个苹果只有1种分法
        for(int i = 1; i <= m; i++)
            for(int j = 1; j <= n; j++){
                if(i < j)
                    dp[i][j] = dp[i][j - 1];
                else
                    dp[i][j] = dp[i][j - 1] + dp[i - j][j];
            }
        cout << dp[m][n] << endl;
    }
    return 0;
}

复杂度分析：

• 时间复杂度：$O\left(nm\right)O(nm)$O(nm)，遍历二维数组
• 空间复杂度：$O\left(nm\right)O(nm)$O(nm)，二维数组的空间