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