96. Unique Binary Search Trees

https://leetcode.com/problems/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

Constraints:

• 1 <= n <= 19

Solution

1. Recursive (DFS)

class Solution {
public:
    int numTrees(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        int num = 0;
        num += 2 * numTrees(n - 1);
        for (int i = 2; i < n; ++i) {
            num += numTrees(i - 1) * numTrees(n - i);
        }
        return num;
    }
};

2. Optimized using bottom-up DP

class Solution {
public:
    int numTrees(int n) {
        static vector<int> dp{0,1,2};
        while (dp.size() - 1 < n) {
            int num = 0;
            num += 2 * numTrees(dp.size() - 1);
            for (int i = 2; i < dp.size(); ++i) {
                num += numTrees(i - 1) * numTrees(dp.size() - i);
            }
            dp.push_back(num);
        }
        return dp[n];
    }
};

• #dfs

• #dp