# 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]$$

```cpp
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];
    }
};
```