96. Unique Binary Search Trees Leetcode Java

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

Solution:
Eg. for n=4, there are basic 4 cases 1 as root, 2 as root, 3 as root and 4 as root. 
For 1 as root, since 1 is the smallest so there is only one possible for left child which is null res[0], but for the right child, there are 3 possibilities, which are 2, 3, 4 as root respectively. This is essentially the same as 1,2,3 as root so totally 5 unique BSTs(res[3]=5). 
For 2 as root, 1 possibility for left child which is 1 as the leaf(res[1]). For right child, totally 2 unique BSTs(res[2]=2). 
For 3 as root, just the opposite of last case, left=res[2],right=res[1] 
For 4 as root, opposite of first case, left=res[3], right=res[1] 
Through this analysis, we can deriver the recursion equation, res[n]=Sum(res[i]*res[n-1-i]), where i is from 0 to n-1. 
Time complexity： O(n^2)

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

As some people may already notice, this is the Catalan number, which is commonly used to find the valid Dyck words, valid parenthesis... Mathematically, the problem can be simplified by this equation:

  public int numTrees(int n) {  
     int res=1;  
     for(int i=1;i<n;i++){  
     res=2*res*(2*i+1)/(i+2);  
     }  
     return res;  
   }