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.
再次感觉智商被碾压。。。第一感觉就是需要找规律，往dp的方向靠。。。然而并没有看出什么规律。。。
一定要牢记BST的一个重要特性！！！
中序遍历BST，实际得到的是一个sorted array！！！
OK，那如何利用这个特性得到解呢？
对于包含1,2,...,n这n个数的所有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)，我们需要求解当root为i时，可能有多少unique BST，也就是需要先求F(i, n)。
下面进入关键的一步，让我们来分析一下F(i, n)的求解：
假设n=7,i=3，所有unique BST中序遍历后都会得到[1,2,3,4,5,6,7]。
考虑以3为root的所有BST，一共有多少种可能呢？
我们先看左子树，此时对应[1,2]，有G(2)种树的形式。
再看右子树，此时对应[4,5,6,7]，由于同样是一个递增数列，树的不同形式与[1,2,3,4]实际上是相同的，所以总共有G(4)种形式。
已知左右各有G(2)与G(4)种可能，那简单的乘法原理就可以知道，对应root=3的BST一共有G(2)*G(4)种可能！！！
也就是：
- F(i, n) = G(i-1) * G(n-i) 1 <= i <= 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
