DP-13. Unique Binary Search Trees

Problem

LeetCode #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:

Explanation

intuition

What is the characteristic of BST? How can we take advantage of this? How to identify unique BST?

Maybe we can make it simple. As at first, we should pick one number as the root node. So, if n = 0, we only have 1 possibility (which is empty tree); if n = 1, we also only have 1 possibility (which is make 1 as the root node).

To solve this problem, we need two functions.

  • f(k, n) means when we pick k as the root node out of n, the number of unique BSTs.
  • g(n) means given n, the number of unique BSTs.

When n = 2, we have 2 choices to pick a root node, so the whole possibility is g(2) = f(1, 2) + f(2, 2); in the same way, when n = 3, the total possibility if g(3) = f(1, 3) + f(2, 3) + f(3, 3); But we can deal with f(k, n)? Take an example, if n = 5, and we pick 3 as the root, as mentioned before, g(5) = f(1, 5) + f(2, 5) + f(3, 5) + f(4, 5) + f(5, 5), how to calculate f(3, 5)? when 3 is the root node, there are 2 nodes on its left and 2 nodes on its right, so f(3, 5) = g(2) * g(n); So, there is overlapping pattern in this problem and we have to use memoization.

Solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public int numTrees(int n) {
int[] dp = new int[n + 1];
dp[0] = 1; 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];
}
}

Time complexity: O(n * n);

Space complexity: O(n);