# 96-Unique Binary Search Trees
###### tags: `Medium`
* Question:
https://leetcode.com/problems/unique-binary-search-trees/
* Key:
1. Dynamic programming
2. how to use two for-loops to get sum of 2 elements in an array.

* Hint:
1. G(N) : Number of unique BST formed using 1 to N
2. 第n個的數目為前面n-1種的兩兩排列組合G(N) = G(0) * G(N) + G(1) * G(N-1) + G(2) * G(N-2) .... + G(N) * G(0)
3. Can use **dynamic programing** to build up upper solution using lower solution as
4. G(N) will need the solutions of G(2), G(3), G(4) .... G(N-1)

class Solution {
public:
    int numTrees(int n) {
        
        // track solutions for each number of nodes 
        vector<int> dp(n+1,0);
        
        // empty node has 1 tree with no root
        dp[0] = 1;
        
        // 1 node has 1 tree with one root
        dp[1] = 1;
        
        // calculate solution for i=2 to n where total node is 2 to n
        for(int i=2;i<=n;i++)
        {
            // for ith iteration problem has i nodes
            // from 1 to ith node each node can be a root 
            // each root has possible trees with G(leftSubtree) * G(RightSubtree)
            // Adding up the solutions for 1 to i gives G(i)
            for(int j=1;j<=i;j++)
            {
                dp[i] += dp[j-1] * dp[i-j];   
            }            
        }
        
        // return number of unique BST trees with n nodes 1 to N
        return dp[n];
    }
};