Unique Binary Search Trees

Description

Given n, how many structurally unique BSTs (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

Let dp[i] be the number of BSTs that stores 1..i. dp[0] = 1 if we consider the tree with root = null is also a BST.

To store 1..n in a BST, we can select i=1,...n as the root node. Then there are i-1 nodes on the left sub-tree and n-i nodes on the right sub-tree. Thus, the number of BSTs that stores 1..n and has i as the root node is dp[i-1] * dp[n-i].

So, the total number of BSTs that stores 1..n is:

$dp[n] = \sum_{1 \le i \le n} dp[i-1] \cdot dp[n-i]$

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = dp[1] = 1;
        for(int len = 2; len <= n; ++len){
            for(int i = 0; i < len; ++i){
                dp[len] += dp[i] * dp[len - 1 - i];
            }
        }
        return dp[n];
    }
};