Unique Binary Search Trees (LeetCode Tree)

Question: 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

Idea: Do not consider 1, 2, 3, 4 as numbers, just consider them as variables or algebraic symbols, e.g. v1<v2<v3<v4<v5.., vi, ..,vn. The values make no sense in this problem.

If we pick vi as the root, the left subtree is formed by v1->vi-1, the right subtree is formed by vi+1->vn. Since the left subtree and the right subtree are independent, the number of different trees rooted at vi is  numLeft*numRight, where numLeft is the number of subtrees formed by v1->vi-1 (i-1 symbols), the numRight is the number of subtrees formed by vi+1->vn (n-i-1 symbols).

So the algorithm is obvious: for each symbol vi, use it as the root, get the numLeft*numRight=num(i-1 symbols)*num(n-i-1 symbols). Accumulate the total number of all the roots v1->vn, we can have the final result.

Time: O(n) Space: O(n)

Code:

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