Little Ginger got an assignment from her teacher: how many ways are there to put 4 apples in 2 baskets. There are no differences between apples and baskets. It?s easy for Ginger to solve, since she can enumerate all the cases, which are {0, 4}, {1, 3} and {2, 2}.
How about we crank it up a notch? Now, there are M apples and N baskets, (N and M won?t exceed 100), how many ways are there?

输入格式

Multiple input cases! Two positive integers M and N in a single line for each case.

输出格式

Print the answer in a single line.

样例输入

6 4
3 2

样例输出

9
2

 预处理出所有的结果，直接查表即可。

#include<stdio.h>
int dp[101][101];
int main(){
	int i,j;
	for(i=0;i<101;i++)
	dp[0][i]=1;
	for(i=0;i<101;i++)
	dp[1][i]=1;
	for(i=2;i<101;i++)
	dp[i][0]=1;
	for(i=2;i<101;i++)
	dp[i][1]=1;
	for(i=2;i<101;i++)
	for(j=2;j<101;j++)
	if(i>=j) 
	dp[i][j]=dp[i-j][j]+dp[i][j-1];
	else
	dp[i][j]=dp[i][i]; 
	/*for(i=1;i<=10;i++){
		for(j=1;j<=10;j++)
		printf("%d ",dp[i][j]);
		printf("\n");
	}*/
	while(scanf("%d %d",&i,&j)==2){
		printf("%d\n",dp[i][j]);
	}
	return 0;
}