卡特兰数问题：1. 有一个无限大的栈，一共n个元素，请问有几种合法的入栈出栈形式？

                    2. 排队买电影票的问题，有2n个人排队买票，其中有n个人只有一张50元纸币，另外n个人只有一张100元的硬币，售票员没有零钱，问这2n个人应该怎样排队，才能使得不冲突，每个人都能买到票。

                    3. 矩阵A1A2A3......An相乘，求所有可能的相乘顺序，括号如何放置。

                    4. 值由1~n的n个节点构成的二叉树搜索树的个数？

以上这些都是卡特兰数问题：h(n)=h(0)*h(n-1)+h(1)*h(n-2)+...+h(n-1)*h(0)

计算的解决方法：用动态规划的思想，顺序求出每个h(i)，i从0到n。

#include<iostream>#include<vector>using namespace std;int cal(int n){    vector<int> h(n+1,0);    h[0]=1;    h[1]=1;    for(int i=2;i<=n;i++)    {        for(int j=0;j<i;j++)            h[i]+=h[j]*h[i-j-1];    }    return h[n];}int main(){    int n;    cin>>n;    int result=cal(n);    cout<<result<<endl;}

卡特兰数计算 动态规划思想