题目大意：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。

输入

输出

样例输入

1
7 3

样例输出

8

解题思路

不同习惯m个苹果n个盘子，不妨看成是n个苹果m个盘子，用f[n][m]来表示。下面分类讨论：

如果盘子比苹果多，即m>n，那么肯定有m-n个空盘子，空盘子没用，直接不要就行了，f[n][m] = f[n][n]。

否则m<=n，又有两种情况——要么有空盘子，要么没有空盘子，两种情况加起来就是f[n][m]：如果有空盘子（至少1个），空盘子还是不要，f[n][m] += f[n][m-1]，如果没有空盘子，先每个盘子各放一个苹果，转换成n-m个苹果放到m个盘子，即f[n][m] += f[n-m][m]。

最后考虑赋初值问题。显然，只有一个盘子或者一个苹果，方案数都是1。然后再看看递推式，如果从2开始推，-1之后最小是1，已经有初值了，但是n-m是在m<=n的情况下出现的，有可能为0，故需要把f[0][1~m]赋初值。

程序实现