#include <stdio.h>
/*计算catlan数f(n)，其递推式如下：
         1                  n=0 || n=1
f(n)={ ∑f(i)*f(n-1-i)         n>1，其中i∈[0,n-1]范围整数
例如
f(2)=f(0)*f(1)+f(1)*f(0)=2
f(3)= f(0)*f(2)+f(1)*f(1)+f(2)*f(0)=2+1+2=5
f(4)= f(0)*f(3)+f(1)*f(2)+f(2)*f(1)+f(3)*f(0)=5+2+2+5=14
f(5)= f(0)*f(4)+…+f(4)*f(0)=42
输出f(n) 

…
这是一个在很多问题中出现的数列。
由于这个数列的值递增很快，现在我们只想输出f(n)除以10000007的余数。请写出dp写法一、写法二。
【注：由于f(n)要用到f(0),f(1)…f(n-1)的值，所以不能写压缩型dp】
//有意思的是，上面的f(n)=C(2n,n)/(n+1)  比如f(3)=C(6,3)/4=20/4=5

*/

long long dp[10000];

long long f(int k)
{
	int i;
	if (k < 0)
	{
		return 0;
	}
	if (dp[k])	return dp[k];
	if (0 == k || 1 == k)
	{
		return dp[k] = 1;
	}
	else
	{
		for (i = 0; i < k; ++i)
		{
			dp[k] += ((f(i) % 10000007) * (f(k - 1 - i) % 10000007)) % 10000007;
		}
		return dp[k] % 10000007;
	}
}

int main()
{
	int i;
	for(i=1;i<100;i++)//打印f(1)---f(19) 
	    printf("%lld\n", f(i));
	return 0;
}

========================================Talk is cheap, show me the code=======================================