[Leetcode] Unique Binary Search Trees

Problem

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

Algorithm

Recursive

Given values from L to R, we can select K as the root. Then recursively solve the subproblems L to K-1, and K+1 to R, K goes from L(inclusive) to R (inclusive). 

        Number of subtrees rooted with K = Number of left subtrees * Number of right subtrees. 

Sum over all. 

DP 

We can use DP to solve this problem. Note the number of unique trees only depends on the number of  values available. For example, BST containing values [1,2,3] has the same number of unique trees as BST containing values [4,5,6]. Let dp[i] be the number of unique trees using i values. dp[0] = 1, dp[1] = 1. Using one value as the root, we have (i-1) options to distribute the rest (i-1) values to left subtree and right subtree. Let k = number of values distributed to left subtree, and k can goes from 0 to i-1. 

Code