96 Unique Binary Search Trees

1. Recursive (Time Limit Exceed)

int numTrees(int n)
{
    if (n == 0 || n == 1)
        return 1;
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        res += numTrees(i - 1) * numTrees(n - i);
    }
    return res;
}

Space	Time
$O(log(n))$	$O(c^n)$

2. Recursive + Memoization

int numTrees(int n)
{
    static map<int, int> m;
    if (m.count(n))
        return m[n];
    if (n == 0 || n == 1)
    {
        m[n] = 1;
        return 1;
    }
    int res = 0;
    for (int i = 1; i <= n; i++)
    {
        res += numTrees(i - 1) * numTrees(n - i);
    }
    m[n] = res;
    return res;
}

Space	Time
$O(n)$	$O(n)$