14019 - 放苹果

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

注：5，1，1 和 1，5，1 是同一种放法（因为盘子相同，顺序无关）。

第一行包含一个整数 t （ 0 < t \le 20 ），表示测试数据的组数。

接下来 t 行，每行包含两个整数 M 和 N （ 1 \le M, N \le 10 ），分别表示苹果数和盘子数。

对于每组数据，输出一行一个整数，表示对应的放法总数 K 。

数据范围与约定

• 1 \le M, N \le 10
• 0 < t \le 20

提示

这是一个经典的递归/动态规划问题。

设 f(m, n) 表示将 m 个苹果放入 n 个盘子中的方法数。考虑两种情况：

1. 至少有一个盘子空着：此时方法数为 f(m, n-1) 。
2. 所有盘子都非空：则每个盘子先放一个苹果，剩下 m-n 个苹果随意放入 n 个盘子，方法数为 f(m-n, n) 。

因此递推式：

f(m, n) =

1, m = 0 或 n = 1

f(m, m), n > m

f(m, n-1) + f(m-n, n), m \ge n

• 当 m = 0 时，只有一种放法（所有盘子都空）；
• 当 n = 1 时，只有一种放法（所有苹果放在这一个盘子里）；
• 当 n > m 时，空盘子不影响结果，等价于 f(m, m) 。

用递归或动态规划均可，由于数据范围很小，递归即可。