0096. 不同的二叉搜索树 [Medium] [Unique Binary Search Trees].md

96. Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?

Example:

Input: 3
Output: 5
Explanation:
Given n = 3, there are a total of 5 unique BST's:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

---

题目：计算由1~n这n个数能构成的二叉查找树的个数。

思路：参考DP Solution in 6 lines with explanation. F(i, n) = G(i-1) * G(n-i)。先计算长度为i的二叉查找树BST的个数dp[i]：不同的root结点会有不同的BST，假设根结点取j，那么左子树由1...j-1构成(长度j-1)，右子树由j+1...i构成（长度i-j）；这里使用了一个技巧：只要长度相同，那么其对应的不同的BST个数是相同的，即对于子树1,2,3和4,5,6长度均为3，那么它们所有的BST个数是相同的。由此可以推导出状态转移方程：dp[i] += dp[j-1] * dp[i-j]。

The tricky part is that we could consider the number of unique BST out of sequence [1,2] as G(2), and the number of of unique BST out of sequence [4, 5, 6, 7] as G(4).

工程代码下载

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1);
        //sequence of length 1 (only a root) or 0 (empty tree)
        dp[0] = dp[1] = 1;

        //不同长度
        for(int i = 2; i<=n; ++i){
            //不同的根结点
            for(int j = 1; j <= i; ++j){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }

        return dp[n];
    }
};