Question
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 1 2 3 3
\ \ / \ / /
2 3 1 3 1 2
\ / \ /
3 2 2 1
求解过程
思路：1...n之间的所有BST数量等于以1...n之间的每个数为根节点的BST之和。
G(n)：表示1...n之间的所有BST数量
F(i,n)：表示以i为根节点的BST数量
G(n)=F(1,n)+F(2,n)+...+F(n,n)
F(i,n)=G(i-1)*G(n-i)
注：
1...i...n以i为根节点的时候，BST数量等于以1...(i-1)组成的左子树数量乘以(i+1)...n组成的右子树，(i+1)...n组成的BST数量等1...(n-i)能构成的BST数量.
递推公式：
G(n)=G(0)*G(n-1)+G(1)*G(n-2)+...+G(n-1)*G(0) G(0)=1
实现代码
public static int countOfBSTNumber(int n) {
if (n < 0) return -1;
int[] C = new int[n + 1];
C[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j < i; j++) {
C[i] += C[j] * C[i - j - 1];
}
}
return C[n];
}
分析：
n is ：1， the number of BST is : 1
n is ：2， the number of BST is : 2
n is ：3， the number of BST is : 5
n is ：4， the number of BST is : 14
n is ：5， the number of BST is : 42
n is ：6， the number of BST is : 132
n is ：7， the number of BST is : 429
n is ：8， the number of BST is : 1430
n is ：9， the number of BST is : 4862
n is ：10， the number of BST is : 16796
n is ：11， the number of BST is : 58786
n is ：12， the number of BST is : 208012
n is ：13， the number of BST is : 742900
n is ：14， the number of BST is : 2674440
n is ：15， the number of BST is : 9694845
n is ：16， the number of BST is : 35357670
n is ：17， the number of BST is : 129644790
n is ：18， the number of BST is : 477638700
n is ：19， the number of BST is : 1767263190
n is ：20， the number of BST is : -2025814172
可以看到当n=20的时候，所构成的BST的数量以前超过了int能够表示的数范围了。
