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

-------------------- thinking ---------------------------------------
https://oj.leetcode.com/discuss/17674/dp-problem-10-lines-with-comments

---------------------- codes ----------------------------------------
class Solution {
public:
    int numTrees(int n) {
       vector<int> num(n + 1, 0);
       num[1] = 1;
       for (int i = 2; i < n+1; i++) {
           //situation of two edge ele as root of the tree
           int result = 2 * num[i-1];
           for (int j = 1; j < i-1; j++) {
               //situation of inside eles as root of the tree
               result += num[j] * num[i-j-1];
           }
           num[i] = result;
       }
       return num[n];
    }
};