代码语言：javascript复制
#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("%lldn", f(i));
return 0;
}
