卡特兰数问题：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; }