P1044 栈（卡特兰数）

思路：卡特兰数和动态规划。
卡特兰数：一个栈（无穷大）的进栈序列为1,2，3，…n，问有多少个不同的出栈序列。
设f(n)为序列个数是n的出栈序列种数。首先设最后出栈的元素为k，（k取不同值是相互独立的，所以所有的k的出栈情况可用加法原则）。由于k最后出栈，所以比k小的元素都已经出栈了，此处有f(k-1)种，而之后比k大的入栈，且在k之前出栈，此处有f(n-k)种方式。因为二者相互独立，所以总共有f(k-1)*f(n-k)种。而k可以选择1到n，再根据加法原则将不同值的序列总数相加，总序列种数为：f(n)=f(0)*f(n-1)+f(1)*f(n-2)+…+f(n-1)*f(0).所以，得到递推式：
设h(n)为卡特兰数的第n+1项，令h(0)=1,h(1)=1,递推式为：
h(n)=h(0)*h(n-1)+h(1)h(n-2)+…+h(n-1)h(0).(n>=2)
另类递推式：h(n)=h(n-1)(4n-2)/(n+1)

f(0) = 1;

f(1) = 1;

f(2) = f(0)*f(1) + f(1)*f(0);

f(3) = f(0)*f(2) + f(1)*f(1) * f(2)*f(0);

f(n) = f(0)*f(n-1) + f(1)*f(n-2) + …+ f(n-2)*f(1) + f(n-1)*f(0)

```cpp
#include<iostream>
using namespace std;
int main()
{
    int a[20]={0};
    int n;
    cin>>n;
    a[0]=1;
    a[1]=1;
    for(int i=2;i<=n;i++)
        for(int j=0;j<i;j++)
        a[i]=a[i]+a[j]*a[i-1-j];
    cout<<a[n]<<endl;
    return 0;
}