<---大佬们点个赞吧qwq

$$\huge\color{orange}{→→→暑假每日一题2022题解合集←←←}$$
$\ $
$\ $

题目描述

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

盘子相对顺序不同，例如 $5，1，1$ 和 $1，5，1$ 算作同一种分法。

输入格式

输入包含多组测试数据。

每组数据占一行，包含两个整数 $M$ 和 $N$。

输出格式

每组数据，输出一行一个结果表示分法数量。

数据范围

$1 \\le M,N \\le 10$

输入样例：

7 3

输出样例：

8

算法 1

(dp) $O(mn)$

把 $f(i,j)$ 定义为把 $i$ 个同样的苹果放在 $j$ 个同样的盘子里的分法数量，则答案就是 $f(n,m)$。
如何求 $f(i,j)$ 呢？分以下两种情况来讨论：

1. $i<j$
2. $i\ge j$

当 $i<j$ 时，一定会剩下 $j-i$ 个空盘子，这些空盘子不会对结果产生影响，所以就相当于求 $f(i,i)$。
当 $i\ge j$ 时，再分两种情况讨论：

1. 至少有 $1$ 个盘子空着
2. 所有盘子中的苹果数量都至少为 $1$

如果至少有 $1$ 个盘子空着，那么这个盘子不用考虑，相当于 $f(i,j-1)$。
如果所有盘子中的苹果数量都至少为 $1$，那么完全可以把所有盘子中的苹果数量都减 $1$，就相当于 $f(i-j,j)$

所以当 $i\ge j$ 时，$f(i,j)$ 相当于 $f(i,j-1)+f(i-j,j)$。

由此可列出状态转移方程（还要考虑边界情况，比如 $i=0$ 或 $j=1$）：
$$f(i,j)= \begin{cases} \qquad\qquad1\quad\qquad\qquad\qquad\text{if}\ i=0\ \text{or}\ j=1\\\ \qquad\quad f(i,i)\qquad\qquad\qquad\text{if}\ i\ne0\ \text{and}\ j\ne1\ \text{and}\ i<j\\\ f(i,j-1)+f(i-j,j)\quad\ \ \ \text{otherwise} \end{cases}$$

时间复杂度

只需要把 $f(0,0),f(0,1)\cdots f(m,n)$ 这 $mn$ 个数推出来即可，时间复杂度是 $O(mn)$。

空间复杂度

把 $f(0,0),f(0,1)\cdots f(m,n)$ 这 $mn$ 个数存下来需要 $O(mn)$ 的空间，所以空间复杂度是 $O(mn)$。

C++ 代码

#include <iostream>

using namespace std;

const int N = 12;

int m, n;
int f[N][N]; // f[m][n] 表示把 m 个同样的苹果放在 n 个同样的盘子里的分法数

int main()
{
    for (int i = 0; i < N; i ++ ) f[i][1] = 1; // 把 i 个苹果放在 1 个盘子里，只有 1 种方案
    for (int i = 0; i < N; i ++ ) f[0][i] = 1; // 把 0 个苹果放在 i 个盘子里，也只有 1 种方案

    for (int i = 1; i < N; i ++ ) // 枚举苹果数
        for (int j = 2; j < N; j ++ ) // 枚举盘子数
            if (i < j) f[i][j] = f[i][i]; // 如果苹果数 < 盘子数，则必定有 (盘子数 - 苹果数) 个空着的盘子，可以将这些空着的盘子去掉
            else f[i][j] = f[i][j - 1] + f[i - j][j]; // 苹果数 ≥ 盘子数，分两种情况讨论，可以有一个盘子空着，也可以每个盘子至少放 1 个

    while (cin >> m >> n) cout << f[m][n] << '\n';

    return 0;
}

算法 2

(递归) $O(?)$

其实就是函数版的算法 1

时间复杂度

呃……不知道耶，知道的大佬们请发在评论区里，谢谢！

空间复杂度

还是不知道 ·-·

C++ 代码

#include <iostream>

using namespace std;

int f(int m, int n) // f(m, n) 表示把 m 个同样的苹果放在 n 个同样的盘子里的分法数
{
    if (n == 1 || !m) return 1; // 把 i 个苹果放在 1 个盘子里或把 0 个苹果放在 i 个盘子里，都只有 1 种方案
    if (m < n) return f(m, m); // 如果苹果数 < 盘子数，则必定有 (盘子数 - 苹果数) 个空着的盘子，可以将这些空着的盘子去掉
    return f(m, n - 1) + f(m - n, n); // 苹果数 ≥ 盘子数，分两种情况讨论，可以有一个盘子空着，也可以每个盘子至少放 1 个
}

int m, n;

int main()
{
    while (cin >> m >> n) cout << f(m, n) << '\n';

    return 0;
}

算法 3

(dfs) $O(?)$

只需要枚举下一个数即可（注意顺序，$5，1，1$ 和 $1，5，1$ 是一样的，所以必须按一种顺序枚举，这里采用从小到大）

时间复杂度

bzd :(

空间复杂度

bzd

C++ 代码

#include <iostream>

using namespace std;

int dfs(int last, int m, int n) // last: 上个盘子里的苹果数
{
    if (last * n > m) return 0; // 苹果太多了，无解（注意：这个一定要放在下一个的前面）
    if (n == 1 || m == 0) return 1; // 把 i 个苹果放在 1 个盘子里或把 0 个苹果放在 i 个盘子里，都只有 1 种方案

    int res = 0;
    for (int i = last; i <= m; i ++ ) res += dfs(i, m - i, n - 1); // 枚举可能的这个盘子里的苹果数（因为是从小到大，所以这个盘子里的苹果数必须大于 last

    return res;
}

int m, n;

int main()
{
    while (cin >> m >> n) cout << dfs(0, m, n) << '\n'; // 盘子里的苹果数不可能小于 0

    return 0;
}