NOI2.3-666放苹果
6167+
作者：crxis 发布：2017-06-25 分类：递推
题目大意：把M个同样的苹果放在N个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？（用K表示）5，1，1和1，5，1 是同一种分法。
输入
第一行是测试数据的数目t（0 <= t <= 20）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=10。
输出
对输入的每组数据M和N，用一行输出相应的K。
样例输入
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]赋初值。
程序实现
