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數(shù)量等于以1...n之間的每個數(shù)為根節(jié)點的BST之和。
G(n)：表示1...n之間的所有BST數(shù)量
F(i,n)：表示以i為根節(jié)點的BST數(shù)量
G(n)=F(1,n)+F(2,n)+...+F(n,n)
F(i,n)=G(i-1)*G(n-i)
注：
1...i...n以i為根節(jié)點的時候，BST數(shù)量等于以1...(i-1)組成的左子樹數(shù)量乘以(i+1)...n組成的右子樹，(i+1)...n組成的BST數(shù)量等1...(n-i)能構(gòu)成的BST數(shù)量.
遞推公式：
G(n)=G(0)*G(n-1)+G(1)*G(n-2)+...+G(n-1)*G(0) G(0)=1
實現(xiàn)代碼
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的時候识窿，所構(gòu)成的BST的數(shù)量以前超過了int能夠表示的數(shù)范圍了斩郎。
