class Solution {
public:
int numTrees(int n) {
// We use a vector to memoize subproblem's results:
int results[n + 1];
results[0] = 1;
for (int i = 1; i <= n; ++i) {
// Every iteration uses previous iterations results:
results[i] = numTreesRec(results, i);
}
return results[n];
}
int numTreesRec(const int* results, int n) {
int res = 0;
// Calculates the combinations generated when the root node is
// one on the left half of the set:
int hn = n / 2;
for (int i = 0; i < n / 2; ++i) {
res += results[i] * results[n  (i + 1)];
}
// For combinations generated when the root node is one of the
// right half we know that is the same as the former step, hence
// we just multiply by two:
res *= 2;
// If n is odd we need to add the combinations when the middle node is root:
if (n & 1) {
int i = n / 2;
res += results[i] * results[n  (i + 1)];
}
return res;
}
};
Solution based on dynamic programming O(n^2) instead of exponencial


I'm not sure why your solution must be so long. There's no need to divide by 2 in the solution. This is my DP solution using C++:
int numTrees(int n) {
// array[i] contains the number of unique BSTs containing i nodes. int array [n + 1]; array[0] = 1; for(int i = 1; i <= n ; i++) { array[i] = 0; for(int numNodes = 0; numNodes <= i  1; numNodes++) { array[i] += array[numNodes] * array[i  1  numNodes]; } } return array[n];
}
Note that my recursive solution, which ran in exponential time, was also accepted.
int numTrees(int n) {
if(n == 0) return 1; int sum = 0; for(int i = 0; i <= n  1; i++) { sum += numTrees(i) * numTrees(n  1  i); } return sum;
}

Since the number of node configurations in the left subtree, LEFT, is independent of the number of node configurations in the right subtree, RIGHT, the total number of node configurations in a given tree with k nodes in the left subtree and (n  1  k) nodes in the right subtree is given by LEFT * RIGHT.
This is why you take the product of those two array values.

One could only produce this solution if they solved the recursive formula. Otherwise, in most interview situations, you wouldn't have enough time to perform the mathematics behind this.
That being said, it's cool if you find the constant space solution. Maybe an interviewer would appreciate this solution more than a DP solution?

My idea is similar to yours, but maybe its more clear to understand. We use DP to store total number of unique BST for each n. When calculate that, we separate the array (1...n) by choosing roots from 1 to n, then we can multiply left situation by right situation, and sum them up.
Here is the code://using DP to avoid duplicate calculate class Solution { public: int numTrees(int n) { unordered_map<int, int> hashmap; hashmap[0] = 1; hashmap[1] = 1; //store total number of unique BST for n if(n == 0  n == 1) { return n; } for(int i = 2; i <= n; ++i) { //calculate unique BST when there is i numbers int total = 0; for(int j = 1; j <= i; ++j) { //calculate uniques BST when j is root total += (hashmap[j  1] * hashmap[i  j]); //multiply left and right } hashmap[i] = total; } return hashmap[n]; } };

An hashmap with hash function hash(n) { return n } with max n known at the beginning, implodes into a vector<int>. But since N is known if your compile support C99 or C++11 you can just use a simple vector int vect[n] that is even faster because everything is in the stack. Faster than mine because you don'thave the overhead of the recursive calls.
You can replace it to obtain a litle performance improvement.