Unique Binary Search Trees

Problem Statement

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

[sourcecode language="cpp"]
class Solution {
public:
int numTrees(int n) {

if( n < 3 )
return n;
int i,j;
vector numBST(n+1,0); /* numBST[i] - Number of Bst's upto i */
numBST[0] = 1; /* '1' is just for multiplication */
numBST[1] = 1;
numBST[2] = 2;
for(i=3;i<=n;i++)
{
int cnt = 0;
for(j=1;j<=i;j++)
{
int left = j-1; /* No. of Elements in left side */
int right = i-j; /* No. of Elements in right side */

cnt += numBST[left] * numBST[right];
}
numBST[i] = cnt;
}

return numBST[n];
}
};
[/sourcecode]