LeetCode 96. Unique Binary Search Trees

Problem

LeetCode 96. Unique Binary Search Trees

1. 题目简述

给一个正整数n，节点为（1, 2, 3…n），计算出所有可能存在的BST树的个数。例如：

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

2. 算法思路

动态规划

我们假设函数G(n)为所有可能存在的BST树的个数；函数F(i,n)为以i为根节点，存在的所有BST的个数；我们已知G(0)=1，G(1)=1。

那么我们如何求G(n)呢？对于任意的i为根节点时，其中1<= i <= n，节点[1, i-1]必定都在i节点的左子树；节点[i+1, n]必定都在i节点的右子树，左右子树可以为空；此时F(i,n)=G(i-1)*G(n-i)，i取值从1到n，所以如果要计算G(n)，G(n)的根节点有n种可能，需要将这n种都加起来。

$$ G(n)=F(1,n)+F(2,n)+…+F(n,n)=G(0)\times G(n-1)+G(1)\times G(n-2)+…+G(n-1)\times G(0) $$

因此，计算G(n)需要计算出G(1)到G(n-1)。例如：计算G(3)

$$G(3)=F(1,3)+F(2,3)+F(3,3)=G(0)\times G(2)+G(1)\times G(1)+G(2)\times G(0)=2+1+2=5$$

3. 解法

注意推导，过程，算法本身并不难

class Solution {
    public int numTrees(int n) {

        int[] G = new int[n + 1];
        G[0] = G[1] = 1;

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

        return G[n];
    }
}