96. Unique Binary Search Trees

Problem

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

Solution

/**
 * @param {number} n
 * @return {number}
 */
var numTrees = function(n) {
  var dp = [1, 1];
  for (i = 2; i <= n; i++) {
    dp[i] = 0;
    for (j = 1; j <= i; j++) {
      dp[i] += dp[i - j] * dp[j - 1];
    }
  }
  return dp[n];
};

Explain:

例如：有 3 个节点，取 1 个作为 root，还剩 2 个。可以左边 0 个，右边 2 个；左边 1 个，右边 1 个；左边 2 个，右边 0 个。即：F(3) = F(0) * F(2) + F(1) * F(1) + F(2) * F(0)。其中 F(0) = F(1) = 1 。

Complexity:

• Time complexity :
• Space complexity :