Lintcode: Unique Binary Search Trees

Given n, how many structurally unique BSTs (binary search trees) that store values 1...n?

Have you met this question in a real interview? 

Yes

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

Tags Expand 

Catalan Number Dynamic Programming

http://algorithm.yuanbin.me/math_and_bit_manipulation/unique_binary_search_trees.html
The key is to understand that the result is concerned only with how many numbers, not how large these numbers are. And the number of possibilities is a product of element numbers of left and right sides. Which means the sum of al possible left and right numbers' combinations.
When there is 1 number, c[1] = 1;
when there is  2 numbers, c[2] = c[0] * c[1] + c[1] * c[0] = 2 (here we set c[0] = 1)
when 3, c[3] = c[0] * c[2] + c[1] * c[1] + c[2] * c[0] =2 + 1 + 2 = 5
... ...
when i, c[n] = sum(c[i] * c[n - 1 - i]) (0 <= i <= n - 1)

Typical dp problem:
Time: O(n^2)
Space:O(n)

class Solution {
public:
    /**
     * @paramn n: An integer
     * @return: An integer
     */
    int numTrees(int n) {
        // write your code here
        vector<int> count(n + 1, 0);
        count[0] = 1;
        for(int i = 0; i <= n; i++){
            //int sum = 0;
            for(int j = 0; j <= n - 1; j++){
                count[i] += count[j] * count[i - 1 - j];
            }
        }
        return count[n];
    }
};