UVA 10943 - How do you add? 递推

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1884

题目大意：

把K个不超过N的非负整数加起来，使得他们的和为N，有多少种方法？比如N=5，K=2，有6种方法。即0+5,1+4,2+3,3+2,4+1,5+0.

输入N和K，求方法总数除以10^6的余数

思路：

递推，从（n-1，k）种的解+上1不就是答案了么？同理从(n,k-1)中加上个0不也是答案么，

所以有：ans[i][j]=(ans[i][j-1]+ans[i-1][j])%mod;

OK注意初始化，（1，k）的解为k，我们可以1个1，k-1个0，组成的全排列。而(n,1）为1，只能选自己嘛。

#include<cstdio>

const int MAXN=100+10;

const int mod=1000000;

int ans[MAXN][MAXN];

int main()

{

	for(int i=1;i<=100;i++)

	{

		ans[1][i]=i;

		ans[i][1]=1;

	}

	for(int i=2;i<=100;i++)

		for(int j=2;j<=100;j++)

			ans[i][j]=(ans[i][j-1]+ans[i-1][j])%mod;

	int n,k;

	while(scanf("%d%d",&n,&k),n||k)

	{

		printf("%d\n",ans[n][k]);

	}

	return 0;

}