题目的主要信息：

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

方法一：

采用递归。用apples函数实现，放苹果分为两种情况：

有盘子为空：假设有一个盘子为空，则m个苹果放在n个盘子上的问题转化为将m个苹果放在n-1个盘子上。
每个盘子上都有苹果：假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上。

因此(m,n)=(m-n,n)+(m,n-1)。

当m<0时表示已经没有苹果了，不能再分了，结束递归。当m==1||m=0||n==1表示只有0个苹果或者1个苹果或者1个盘子，只有一种放法，结束递归。 alt

具体做法：

#include <iostream>

using namespace std;

int apples(int m, int n){
    if (m < 0){//没有苹果了，不能再分了
		return 0;
    }
	if (m == 0 || m == 1 || n == 1){ //只有0个苹果或者1个苹果或者1个盘子，只有一种放法
        return 1;
    }
    return apples(m-n, n) + apples(m, n-1);//递归计算有盘子为空和每个盘子都有苹果的情况
}

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

复杂度分析：

时间复杂度： $O (2^{n})$ ，递归结构是树的结构，深度为 $2^{n}$ 。
空间复杂度： $O (n)$ ，递归栈的大小最大为 $O (n)$ 。

方法二：

采用动态规划。动态数组dp[i][j]表示i个苹果放在j个盘子里有多少种分法，首先对数组进行初始化，只有0个盘子时，只有一种分法；只有0个苹果时，有1种分法。然后对动态数组进行遍历更新，当i<j时，表示苹果数小于盘子数，有盘子要空着，此时的分法等于空一个盘子出来的分法，即dp[i][j]=dp[i][j-1]；当i>j时，分为两种情况，有盘子空着即dp[i][j-1]和没有盘子空着dp[i-j][j]。最后dp[m][n]即为m个苹果放在n个盘子的分法。

具体做法：

#include <iostream>
#include <vector>

using namespace std;

int main(){
    int  m, n;
    while (cin >> m >> n) {
        int dp[m+1][n+1];//dp[i][j]表示i个苹果放在j个盘子里有多少种分法
        //初始化动态数组
        for (int i = 0; i <= m; ++i){//只有0个盘子时，只有一种分法
            dp[i][0] = 0;
        }
        for (int j = 0; j <= n; ++j){//只有0个苹果时，有1种分法
            dp[0][j] = 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][j] + dp[i][j-1];//分为两种情况，有盘子空着和没有盘子空着
               }
           }
        }
        cout << dp[m][n] << endl;
    }
    
}

复杂度分析：

时间复杂度： $O (m n)$ ，双重for循环。
空间复杂度： $O (m n)$ ，dp数组的大小为 $m n$ 。

题解 | #放苹果#

题目的主要信息：

方法一：

方法二：