手写：n个苹果放在m个盘子里面有多少种方式

这是一道经典递归 / 动态规划题。

通常默认条件是：

• 苹果相同
• 盘子相同
• 盘子可以为空

比如：

7 个苹果放 3 个盘子

问一共有多少种不同放法。

思路

设函数：

f(n, m)

表示 n 个苹果放入 m 个盘子的方案数。

分两种情况讨论

1. 至少有一个盘子为空

那就相当于：

f(n, m - 1)

因为空一个盘子和不用这个盘子是一样的。

2. 每个盘子都至少放一个苹果

那就先给每个盘子放 1 个苹果，先用了 m 个苹果，还剩：

n - m

此时问题变成：

f(n - m, m)

所以递推公式是

f(n, m) = f(n, m - 1) + f(n - m, m)

边界条件

1. 没