LeetCode 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.
再次感覺智商被碾壓斥滤。缤灵。。第一感覺就是需要找規(guī)律，往dp的方向靠毁靶。。幕与。然而并沒有看出什么規(guī)律速兔。。淤齐。
一定要牢記BST的一個(gè)重要特性９赡摇！更啄！
中序遍歷BST稚疹，實(shí)際得到的是一個(gè)sorted array！＜牢瘛内狗！
OK，那如何利用這個(gè)特性得到解呢义锥？
對(duì)于包含1,2,...,n這n個(gè)數(shù)的所有BST而言柳沙，都可以分成root為1或root為2或...root為n，這n種情況拌倍。
可以表示為：
- G(n): the number of unique BST for a sequence of length n.
- F(i, n), 1 <= i <= n: the number of unique BST, where the number i is the root of BST, and the sequence ranges from 1 to n.
- G(n) = F(1, n) + F(2, n) + ... + F(n, n).
我們最后需要求的是G(n)赂鲤，但為了求G(n)，我們需要求解當(dāng)root為i時(shí)柱恤，可能有多少unique BST数初，也就是需要先求F(i, n)。
下面進(jìn)入關(guān)鍵的一步梗顺，讓我們來分析一下F(i, n)的求解：
假設(shè)n=7,i=3泡孩，所有unique BST中序遍歷后都會(huì)得到[1,2,3,4,5,6,7]。
考慮以3為root的所有BST寺谤，一共有多少種可能呢仑鸥？
我們先看左子樹，此時(shí)對(duì)應(yīng)[1,2]矗漾，有G(2)種樹的形式锈候。
再看右子樹，此時(shí)對(duì)應(yīng)[4,5,6,7]敞贡，由于同樣是一個(gè)遞增數(shù)列泵琳，樹的不同形式與[1,2,3,4]實(shí)際上是相同的，所以總共有G(4)種形式。
已知左右各有G(2)與G(4)種可能获列，那簡單的乘法原理就可以知道谷市，對(duì)應(yīng)root=3的BST一共有G(2)*G(4)種可能！；骱ⅰ迫悠！
也就是：
- F(i, n) = G(i-1) * G(n-i) 1 <= i <= n
進(jìn)一步，可以求得G(n)：
- G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)
代碼：
public class Solution {
public int numTrees(int n) {
if (n <= 0) return 1;
int[] dp = new int[n+1];
dp[0] = 1;
dp[1] = 1;
for (int i = 2; i <= n; i++) {
for (int j = 0; j < i; j++) {
dp[i] += dp[j] * dp[i-1-j];
}
}
return dp[n];
}
}
參考：
https://discuss.leetcode.com/topic/8398/dp-solution-in-6-lines-with-explanation-f-i-n-g-i-1-g-n-i/2
