96. Unique Binary Search Trees

Medium

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

解题思路

    刚看到这一题的时候一点思路没有，但是因为是二叉搜索树，所以有个关系是一定的：
      i+1一定是在i的右子树上的。
    这时候结合上面的例子中的5颗二叉搜索树，多看看可以发现：
      可以根据根节点的值来计算相应的unique BST种类数。
    另外，因为在dynamic-programming标签下，我们就直接按照动态规划的方式去解决问题：
    * 先找到合适的通项公式的含义
    * 然后推导出状态转移方程
    * 然后实现代码

分析

我们按照上面说的思路来分析下例题。

1. 定义d(i,j)的含义是：n=i，j为根节点时的unique BST种类数

2. 定义p(i)的含义是：n=i时的unique BST种类数（其实这就是本题通项公式的含义）。所以必然有
   

3. 正式分析开始，借用数学中的归纳法思想：

   • i=1：d(1,1)=1；p(1)=1。

   • i=2：

     • 根节点为1（j=1）时，2肯定在1的右子树上，所以只有1种情况，d(2,1)=1
     • 根节点为2（j=2）时，1肯定在2的左子树上，所以只有1种情况，d(2,2)=1
     • p(2)=d(2,1)+d(2,2)=2

   • i=3：

     • 根节点为1（j=1）时，那2,3一定在1的右子树上，2,3两个数去任意构成BST，这种情况和i=2时一样，所以d(3,1)=p(2)=p(i-1)=2
     • 根节点为2（j=2）时，1必须在2左子树上，3必须在2右子树上，所以只有一种情况，d(3,2)=1
     • 根节点为3（j=3）时，1,2一定在3的左子树上，1,2两个数去任意构成BST，这种情况和i=2时一样，所以d(3,3)=p(2)=p(i-1)=2
     • p(3)=d(3,1)+d(3,2)+d(3,3)=2+1+2=5
     • 这时候就能看出点转移方程的苗头了，我们继续分析

   • i=4：

     • 根节点为1（j=1）时，那2,3,4一定在1的右子树上，2,3,4三个数任意构成BST，这种情况和i=3时一样，所以d(4,1)=p(3)=p(i-1)=5

     • 根节点为2（j=2）时，1在2的左子树上，3,4一定在2的右子树上。1任意构成1个数字的BST子树，当然也就有p(1)种情况，而3,4两个数任意构成BST子树，则有p(2)种可能，因此这种情况会有以下种unique BST的可能：
       
       再深入想以下，2的左右子树有几个元素？很明显：2的左子树应该有1个（元素为1）、右子树有2个（元素为3、4）。更通用地表达为：j的左子树元素个数为j-1个，j的右子树上元素个数为i-j个。所以左子树上数字独自构成的unique BST数为p(j-1)，右子树上数字独自构成的unique BST数为p(i-j)，因此：
       

     • 同理，根节点为3（j=3）时，3的左子树上是1,2，右子树是4，所以d(4,3)=p(2)*p(1)=2

     • 同理，根节点为4（j=4）时，4的左子树上是1,2,3，所以d(4,4)=p(3)=5

     • p(4) = 5 + 2 +2 + 5 = 14

     • 在这里再回看一下i=3和i=4的分析，可以发现d(i,1)=d(i,i)，d(i,2)=d(i,i-1)，... d(i,j)的计算是对称的，所以要算出p(i)，只需要计算一半，乘以2就行了，当然这个只是一个优化点。

     • 到这里其实已经找到了状态转移方程：
       
       可以再代入i=5验证一下。

代码实现

状态转移方程推导出来之后，代码写起来就很简单了。申请个n+1长度的数组，把p[1]~p[n]都记录下来（），返回p[n]就好了。

public static int numTrees2(int n) {
        int[] p = new int[n+1];
        p[1] = 1;
  
        for (int i = 2; i < n+1; i++) {
            int mid = i / 2;
            for (int j = 1; j <= mid; j++) {
                if (j == 1) {
                    p[i] += 2 * p[i-1];
                } else {
                    p[i] += 2 * p[j-1] * p[i-j];
                }
            }
            if (i % 2 == 1) p[i] += p[i-(mid+1)] * p[i-(mid+1)];
        }

        return p[n];
    }