卡特兰数:hdu-2067 小兔的棋盘&&火车出栈问题

卡特兰数,一串神奇的数字,1,2,5,14......

首先了解一下卡特兰数.

卡特兰数（好像很有用的说） - Coco_T的博客 - CSDN博客

类似问题有火车进栈或是棋盘问题.题的链接如下.

首先是火车进栈,

NCWUOJ

然后还有小兔的棋盘.

小兔的棋盘

代码如下.是递归球法,另外还有一个公式,an=(2n!)/(n!(n+1)!);

#include<stdio.h>

long long int we[40][40]={0};

int main()

{

int n;

int d=1;

while(scanf("%d",&n)!=EOF && n!=-1){

we[1][1]=1;

for(int i=2;i<=n+1;i++){

for(int j=1;j<=i;j++){

if(j==1)

we[i][j]=we[i-1][j];    

else if(j==i)    

we[i][j]=we[i][j-1];    

else    

we[i][j]=we[i-1][j]+we[i][j-1];

}

}

printf("%d %d %lld\n",d++,n,we[n+1][n+1]*2);

}

return 0;

}