96. Unique Binary Search Trees
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[];
if(n== || n==)
return ;
catnums[]=;
catnums[]=;
for(int i=;i<=n;i++)
catnums[i]=catnums[i-]*(*i-)/(i+);
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个叶结点的满二叉树的个数。