题目链接：http://zju.acmclub.com/index.php?app=problem_title&id=1&problem_id=1094

卡特兰数能够应用于两个典型问题：

1.出栈合法性：一个栈(无穷大)的进栈序列为1,2,3,...,n。问有多少个不同的出栈序列?

（分析）假定，最后出栈的元素为k。显然，k取不同值时的情况是相互独立的，也就是求出每种k最后出栈的情况数后可用加法原则。

因为k最后出栈，因此。在k入栈之前。比k小的值均出栈。此处情况有f(k-1)种。

而之后比k大的值入栈。且都在k之前出栈。因此有f(n-k)种方式。

因为比k小和比k大的值入栈出栈情况是相互独立的。此处可用乘法原则，f(n-k)*f(k-1)种，求和便是Catalan递归式。

2.凸多边形三角划分：输入凸多边形的边数n。求不同划分的方案数f(n)

（分析）求f(n)的问题等价于——用k把凸多边形分成两部分，这时对于固定的k。

方案数w(k)=凸k多边形的划分方案数乘以凸n-k+1多边形的划分方案数

而k能够从2到n-1连续变化，即f(n)=w(2)+w(3)+...+w(n-1)

最后求和即得到卡特兰数的递推式。

当然，假设求凸多边形最优三角划分时，思路也是从k处断开。然后动态规划求解。

当n不大时，可考虑算好前n个Cartalan数直接返回。

cpp代码：

#include
     
      using namespace std;int main(){        string Cartalan[]={"1","1","2","5","14",                "42","132","429","1430","4862",                "16796","58786","208012","742900","2674440",                "9694845","35357670","129644790","477638700","1767263190",                "6564120420","24466267020"};        int n;        while(cin>>n){           cout<
      
       <