Unique_Binary_Search_Trees

/*
Unique Binary Search Trees

Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

For example,
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
*/

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

//version2:using dynamic programming
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(2,0);
        dp[0]=1;
        dp[1]=1;
        int num=0;
        for (int i=2; i<=n; ++i)
        {
            int temp=0;
            for (int j=0; j<i; ++j)
            {
                temp += dp[j] * dp[i-j-1];
            }
            dp.push_back(temp);
        }
        return dp[n];
    }
};

REMARK:
1. Hard problem. Have no idea. 
IDEA: Use recursion(similar to what we did in the problem: Same Tree or Maximum Depth of Binary Tree) or dynamic programming. 
For recursion, just recursively count the number of left sub tree times number of right sub tree.
For dynamic programming, define dp[n] as the number of unique BST assuming that the BST has n node.
Then dp[n+1] = sum(dp[i]*dp[n-i-1])  i=0:(n-1).
dp[0]=0 //if the tree is empty, then dp[0] can be 0 or 1. But the recusion require dp[0] to be 1.
dp[1]=1 //if the tree has only one node, then there is only one BST.