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 

Naive Way: I just came up with an idea that is similar to what I did in  Unique Binary Search Trees II.
The idea is to use each number i as root node, then the left branch will be what's less than i, the right branch will be what's larger than i. The total number of distinct structure is their product. Thus, sum up the product for all numbers.

A recursive solution popped up.

 public class Solution {  
   public int numTrees(int n) {  
     // base case  
     if(n <= 1){return 1;}  
     // recursion  
     int sum = 0;  
     for(int i = 1;i <= n;i++)  
       sum += numTrees(i-1-0) * numTrees(n-i);  
     return sum;  
   }  
 }  

Use path memorize can reduce the run time from O(2^n) to O(n^2).

 public class Solution {  
   public int numTrees(int n) {  
     Map<Integer, Integer> map = new HashMap<Integer, Integer>();  
     map.put(0,1);  
     map.put(1,1);  
     return numTrees(n, map);  
   }  
   private int numTrees(int n, Map<Integer, Integer> map){  
     // check memory  
     if(map.containsKey(n)) return map.get(n);  
     // recursion  
     int sum = 0;  
     for(int i = 1;i <= n;i++)  
       sum += numTrees(i-1, map) * numTrees(n-i, map);  
     map.put(n, sum);  
     return sum;  
   }  
 }  

Improved Way: In the Discuss, I saw somebody using DP, which is quite similar to the above. It is written by liaison from leetcode.

 public int numTrees(int n) {  
   int [] G = new int[n+1];  
   G[0] = G[1] = 1;  
   for(int i=2; i<=n; ++i) {  
     for(int j=1; j<=i; ++j) {  
       G[i] += G[j-1] * G[i-j];  
     }  
   }  
   return G[n];  
 }  

Also, somebody raise up that this problem follows the Catalan Number. Can use Catalan formula to generate the number.