Given n, how many structurally unique BST's (binary search trees) that store values 1...n?
For example, Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3思路：卡特兰数: c(0)=1, c(1)=1, c(2)=2, c(3)=5, c(4)=14…
卡特兰数的递推关系：
令h(0)=1, h(1)=1
h(n)=C(2n,n)/(n+1) ＝（2*n+1)!/(n+1)!*n! (n=0,1,2,...)
h(n)= h(0)*h(n-1)+h(1)*h(n-2) + ... + h(n-1)*h(0) (n>=2) 例如：h(2)=h(0)*h(1)+h(1)*h(0)=1*1+1*1=2 h(3)=h(0)*h(2)+h(1)*h(1)+h(2)*h(0)=1*2+1*1+2*1=5 以下代码利用的递推关系式： h(n)=h(n-1)*(4*n-2)/(n+1); 注意：使用64位无符号整数（unsigned long long）最高可存储至第33个卡特兰数，再大的则只能用大数来存储了。 class Solution { public: int numTrees(int n) { unsigned long long catnums[33]; if(n==0 || n==1) return 1; catnums[0]=1; catnums[1]=1; for(int i=2;i<=n;i++) catnums[i]=catnums[i-1]*(4*i-2)/(i+1); return catnums[n]; } };
其它卡特兰数的应用：
矩阵连乘：P = A1A2 ... An，一共有几种加括号的方案？h（n-1）
一个足够大的栈的进栈序列为1,2,3,⋯,n时有多少个不同的出栈序列？h（n）
凸多边三角形划分：在一个凸多边形中，通过若干条互不相交的对角线，把这个多边形划分成了若干三角形，给定凸多边形的边数n，求有多少种划分方案？h（n-2）：例：4边形有2种划分方案，5边形有5种，6边形有14种。
求有n+1个叶结点的满二叉树的个数。
转载于:https://www.cnblogs.com/vincent93/p/6686687.html
