LeetCode96. Unique Binary Search

一、原题

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         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

二、题意

给定数字n，求问由1～n的数字所构成的不同二叉搜索树（BST）的数目。

三、思路

先从简单的分析起：

• n = 1：很容易想到结果为1；
• n = 2：很容易想到结果是2；
• n = 3：此时可以考虑成：
• 将数字3插入到数字2的所有BST中，则此时数字3在2的所有BST中的位置都是固定的，也就是将数字3插入到数字2的所有BST后，新生成的树个数等于原来数字2的BST的数目，等于2；
• 将数字3插入到数字1的所有BST中，同理位置也是固定的（1的右子树），但此时有个问题就是2尚未插入到新的二叉树中，则2插入的位置也是固定的，那最终生成的二叉树个数，等于1；
• 最后是3作为根：则考虑将1、2插入到3作为根的BST中，因为3最大，所以1、2插入的位置肯定在3的左子树，就相当于数字2的所有BST作为3的左子树，所以数目等于数字2的BST的数目，等于2；
• 综上：数字3的BST数目为2 + 1 + 2 = 5；
• 尚未能明显总结出规律，继续推断，n = 4：
• 将数字4插入到数字3的BST中，4的插入位置唯一，生成的数量等于3的BST数目，等于5；
• 将数字4插入到数字2的BST中，则4作为右子树，然后再插入数字3，3插入的位置是固定的，又因为2的BST数量为2，所以4的位置有两种，因此该情况生成的BST数目等于2；
• 将数字4插入到数字1的BST中，则4同样作为右子树，此时需要插入数字3和2，此时3和2构成的BST肯定作为4的最字数，所以数量上等于2的BST，等于2；
• 将数字4作为根，所以新生成的BST数量等于数字3的BST数量；
• 综上：数字4的BST数目为5 +２ + 2 + 5 = 14

....

综上，假设要求数目为n的BST数目，dp[i]用来表示数量为i的BST数目：

• n作为根：生成BST数量为等于(n-1)的BST数目：dp[n - 1]；
• n插入到(n-1)的BST中：数量为dp[n - 1]；
• n插入到(n-2)的BST中，则尚未插入的数据还有数字(n-1)，则最终生成的数量为dp[n - 2]
• n插入到(n-3)的BST中，则尚未插入的数据还有数字(n-2)和(n-1)，则最终生成的数量为dp[n - 3] * dp[2]
  ....
• n插入到(n-i)的BST中，则尚未插入的数据还有数字(n - 1)、(n - 2)、...、(n - i + 1)，因为n插入到(n-i)的BST中，则n都是作为右子树且插入位置唯一，所以新生成的数量等于(n - 1)、(n - 2)、...、(n - i + 1)这几个数字构成的BST的数目，所以生成的数目为：dp[n - i] * dp[i - 1]；

故 $$dp[n] = \sum\limits_{i = 1}^{n - 1} (dp[n - i] * dp[i - 1])$$

四、代码

class Solution {
public:
    int numTrees(int n) {
        if(n <= 1){
            return 1;
        }

        int *dp = new int[n + 1];
        dp[0] = 1;
        dp[1] = 1;

        for(int i = 2; i <= n; ++i){
            dp[i] = dp[i - 1];
            for(int j = 1; j < i; ++j){
                dp[i] += dp[i - j] * dp[j - 1];
            }
        }

        int res = dp[n];
        delete[] dp;
        return res;
    }
};