描述

题目描述

首先我们就是有 m 个苹果，有 n 个盘子，然后问我们把这些苹果放到这些盘子里面，问我们有多少种情况，这里我们注意一下，题目中给了一个很重要的点，就是如果5, 1, 1和 1，1，5是同一种情况，那么这个题瞬间就好做了很多，我们就不用考虑这种排列组合的情况了，题意就是这样

注意： 本题有多组输入，注意注意注意

样例解释

7 3

我们现在是有 7 个苹果，和 3 个盘子，我们现在要考虑有多少种的放法，我们用一个最为朴素的思想去想一下这个问题，我们考虑当盘子的数量是1，2，3的时候分别会有多少种情况

当盘子的数量为 1 的时候，我们可以发现我们只有一种的放法 当盘子的数量为 2 的时候，我们可以发现我们有（1，6），（2，4），（3，3）这三种情况 当盘子的数量为 3 的时候，我们可以发现我们有（1，1，5），（1，2，4），（1，3，3），（2，2，3）四种情况

所以我们最后的答案输出是

8

知识点： 递归，搜索，动态规划

难度： 两星

题解

解法一：dfs

思路解析：

首先我们想这么一个简单的问题，在我们刚才暴力枚举的时候，我们用的思路是什么，我们第一次是所有的盘子都给用上，然后我们第二次是少用一个盘子，第三次再少用一个盘子，然后因为我们的排列不影响结果，我们就可以让他是一个从小到大的顺序，这个就很好写，然后我们写dfs，有这么几种办法 我们写dfs的时候我们第一个办法，我们可以画一个搜索树，我们用一个树的结构来帮助我们理解这个dfs的问题，第二种办法就是我们去思考，我们的递归的终止条件，我们每次是怎么变化的一个问题，然后写出我们的递归条件，然后每次往下递归

这里我文字部分给出，递归条件的思考，首先如果我们最后苹果也就是我们的 $m==0m\; ==\; 0$,这个时候，我们是不是没有办法选择了，我们就要返回 1 ，因为这个时候我们是因为上次的操作到了这个点，所以我们要把这一步计算进去，然后我们继续思考，如果我们最后就剩下了一个盘子怎么办，是不是说明我们只有一种方法，就是把我剩下的苹果都放到我们的这个盘子里面，这是我们的两个递归终止的条件，然后我们继续，因为我们前面确定了这么的一个问题，就是如果我们排列不同，那么我们最后的答案是不会受到影响的，所以如果此时当我们的盘子的数量比我们的苹果的数量要大的时候，我们要进行这么一个操作，就是让我们的盘子的数量变成我们的苹果的数量，因为就算我们盘子多了起来，但是5，1，1和1，1，5的贡献是一样的，那么我们没有必要要多的盘子，反而会影响我们的后续的操作，然后还剩下一种什么样子的情况，就是我们的苹果数量大于我们的盘子的数量，我们这个时候有这么的两种的操作，我们可以少用一个盘子，也就是说，我们可以计算的是$dfs(m,n-1)dfs(m,\; n\; -\; 1)$，然后我们因为如果所有的盘子里面都有苹果我们可以让他们所有的盘子的苹果数量都减少一个也就是 $dfs(m-n,n)dfs(m\; -\; n,\; n)$，然后我们把这两种情况相加就是答案

C++代码实现（dfs）

#include <iostream>
using namespace std;

int dfs(int m, int n) {
    if (m == 0) return 1; // 第一种情况，我们的苹果的数量为 0
    if (n == 1) return 1; // 第二种情况，我们只剩下了一个盘子
    if (m < n) return dfs(m, m); // 如果我们的苹果数量小于了我们的盘子的数量，我们让盘子数量等于苹果的数量
    return (dfs(m - n, n) + dfs(m, n - 1)); // 其他情况的时候，我们要计算少一个盘子，和所有盘子拿走一个苹果的情况，最后就是答案
}
void solve() {
    int m, n;
    while(cin >> m >> n) {  // 多组输入我们的 m 和 n
        cout << dfs(m, n) << "\n"; // dfs最后返回的就是我们的答案
    }
}
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}

时空复杂度分析

时间复杂度是$O(2^n)O(2^n)$,解释如下：

首先因为我们是dfs，我们在dfs的时候就是向我说的那样，其实是搜索了一颗树型的结构，也就是我我们要搜索的是树的一个高度，我们树的最大的高度我们可以发现是 $h==nh\; ==\; n$，也就是说我们要进行的操作就是 $2^{n}2^n$ 的，那么我们的这个时间复杂度就是$O(2^n)O(2^n)$的

空间复杂度是 $O(n)O(n)$，解释如下：

因为我们并未引用进来什么新的空间空间都是常数级别的，但是我们要明白这么一个问题，我们的dfs过程其实是一种栈的结构，是系统为我们分配了一个栈，栈的深度是多少呢？其实就是我们树的高度，也就是说我们的空间复杂度是 $O(n)O(n)$ 的

图解代码：

解法二：动态规划

思路解析

首先动态规划最重要的是什么，就是他的状态转移方程，我们如何求取他的这个状态转移方程呢？我们可以想一下我们刚才搜索的那个过程，我们刚才搜索的过程其实是什么，其实就是一个一个从未知，一点点往下分离拨开迷雾的感觉到了我们知道的地方（递归终止的条件），然后我们再是一层层的回溯回去，得到我们要求得解，那我们可以不可以反过来考虑一下，我们从我们已知的一个部分开始往后递推，因为我们的每一步都是一个已知的状态，那么我们就是不需要回溯，但是空间占用会变大，但是时间会变小，我们从我们已经知道的东西，向前递推，最后的终点就是我们需要的那个答案

实现过程 ：首先我们用一个二维数组来表示我们这步的答案，我们的数组定义为$dp[i][j]dp[i][j]$,这个是什么意思呢？就是我们现在有i个盘子，但是我们要放进去j个苹果的方法数是$dp[i][j]dp[i][j]$，然后我们可以按照我们上面的搜索的思路去思考一下这个问题

1. 如果我们的盘子数量大于我们的苹果数量 $i>ji\; >\; j$，那么我们的$dp[i][j]=dp[i][i]dp[i][j]\; =\; dp[i][i]$
2. 如果我们的苹果数量大于我们的盘子数量 $j>=ij\; >=\; i$, 那么我们的$dp[i][j]=dp[i-j][j]+dp[i][j-1]dp[i][j]\; =\; dp[i\; -\; j][j]\; +\; dp[i][j\; -\; 1]$

这个其实就是我们搜索的那个最后一个条件 这些就是我们dp的方程了，然后我们要预先把我们的dp数组初始化好，首先我们的第一个初始化的就是如果我们的苹果数量为0，即$dp[0][]=1dp[0][]\; =\; 1$， 然后同样的如果我们的盘子的数量是1，那么我们的$dp[][1]=1dp[][1]\; =\; 1$其他的情况就是都是等于 0 的

C++代码实现

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

const int N = 20;
int dp[N][N], n, m;
// n个盘子，m个苹果，dp[i][j]代表i个苹果，j个盘子有多少种放的方法

void solve() {    
    while(cin >> m >> n) {
        memset(dp, 0, sizeof dp); // 清空我们的这个二维的dp数组
        for (int i = 1; i <= n; i++) dp[0][i] = 1; // 把苹果数量为1的，选法置为1
        for (int i = 1; i <= m; i++) dp[i][1] = 1; // 把盘子数置为1的，选法置为1
        for (int i = 1; i <= m; i++) { 
            for (int j = 1; j <= n; j++) {
                if (i < j) dp[i][j] = dp[i][i]; // 如果盘子数量大于苹果的数量，那么转移方程
                else dp[i][j] = dp[i - j][j] + dp[i][j - 1]; // 如果苹果数量大于等于盘子的数量，我们将他们转移为二者相加
            }
        }
        cout << dp[m][n] << "\n"; // 输出最后的答案
    }
}   
signed main()
{
    ios::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
    solve();
    return 0;
}

时间复杂度分析

空间复杂度是$O(n\ast m)O(n\; *\; m)$，解释如下：

空间复杂度：因为我们开辟了一个$n\ast mn\; *\; m$的二维数组，其他的对于它来讲都是极小的所以我们可以把我们的这个空间复杂度看成是$O(n\ast m)O(n\; *\; m)$ 的

时间复杂度是$O(n\ast m)O(n\; *\; m)$，解释如下：

时间复杂度：首先我们的这个dp，相对于我们的搜索，它少了一个回溯的过程，那么我们的复杂度就会降低了很多，我们只是从我们的那个搜索树的终点递推回到答案，然后我们是一个两个的的for循环，是$n+mn\; +\; m$的，然后我们的其它操作就是清空我们的dp数组，这里我们也是双层for循环，然后这里总体的时间就是$n\ast m+n+mn\; *\; m\; +\; n\; +\; m$，然后我们的时间复杂度取的是瓶颈的时间复杂度，那么我们这个的总体的时间复杂度就是$O(n\ast m)O(n\; *\; m)$的