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

Analysis:

DP works well in this problem.

For each sequence from 1 to n, # of BSTs equals:
Sum of BSTs where each number (from 1 to n) is considered as the root node.
For each node, # of BSTs equals:
# of bsts of its left child times # of bsts of its right child.


Denote bst[i] = the number of BSTs can be constructed that store values from 1..n.

n = 1,  Node = {1},      bst[1]  = 1

n = 2,  Node = {1, 2}
when 1 is the root node, there is 1 bst
   1
    \
    2
when 2 is the root node, there is 1 bst
   2
  /
1
bst[2] = 2

n = 3,  Node = {1, 2, 3}
when 1 is the root node, bst[3] =  bst[3] + bst[2] where stores 2 values (2 and 3)
1                                                   1                   1
 \                                 =                 \                    \
 BSTs of {2,3}                              2                    3
                                                       \                   /
                                                        3                2
when 2 is the root node, bst[3] =  bst[3] + bst[1] + bst[1]
          2
         /  \
        1   3
when 3 is the root node, bst[3] =  bst[3] + bst[2] where stores 2 values (1 and 2)
                   3                                 3                   3
                /                 =                 /                    /
 BSTs of {1,2}                            2                   1
                                                   /                       \
                                                 1                         2

Code(C++):

class Solution {
public:
    int numTrees(int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> table(n+1,0);
        if (n==0){return 0;}
        table[0]=1;
        table[1]=1;
        table[2]=2;
        for (int i=3;i<=n;i++){
            int res=0;
            for (int j=0;j<=i-1;j++){
                res = res+ table[j]*table[i-1-j];
            }
            table[i]=res;
        }
        return table[n];   
    }
};

Code(Python):

class Solution:
    # @return an integer
    def numTrees(self, n):
        if n <= 1:
            return 1
        res = [0 for x in range(n + 1)]
        res[0] = 1
        res[1] = 1
        i = 2
        while i <= n :
            for j in xrange(i):
                res[i] = res[i] + res[j]* res[i-j-1]
            i = i + 1
        return res[n]