分苹果（整数划分）

Orange the Apple

Time Limit: 1000MS Memory limit: 65536K

题目描述

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

输入

第一行是测试数据的数目t（0 <= t <= 100）。以下每行均包含二个整数M和N，以空格分开。1<=M，N<=200。

输出

对输入的每组数据M和N，用一行输出相应的K。

示例输入

1
7 3

示例输出

8

递推：

m表示盘子数，n表示苹果数

当m=1时，只有一种方法，所以a[i][1]=1;

当n=1时，只有一种方法，所以a[1][j]=1;

分为三种情况：

当m=n时，a[n][m]=a[n][m-1]+1；

当m>n时，a[n][m]=a[n][n];

当m<n时，分两部分（1）至少有一个盘子没有苹果:a[n][m-1]

                  (2) 先拿出m个苹果，一个盘子放一个苹果，然后再将n-m个苹果放入m个盘子里：a[n-m][m]

         即a[n][m]=a[n][m-1]+a[n-m][m];

第一种和第三种在代码中可一起处理

即借用a[0][j]=1来存储；

代码：