Given n, how many structurally unique BST's (binary search trees) that store values 1 ... n?
Example:
Input: 3
Output: 5
Explanation:
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
class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int     
         """
         M = [0 for x in range(n)]
         M[0] = 1
         for i in range(1,n):
             for j in range(1,i):
                 M[i] += M[j-1] * M[i-j-1]
             M[i] += M[i-1] * 2
         return M[n-1]
class Solution:
     def numTrees(self, n):
         """
         :type n: int
         :rtype: int     
         """
         M = [0 for x in range(n)]
         M[0] = 1
         for i in range(1,n):
             for j in range(1,i):
                 M[i] += M[j-1] * M[i-j-1]
             M[i] += M[i-1] * 2
         return M[n-1]