**LEETCODE-96 Unique Binary Search Trees NOTE**

題目求給定1~n之數字可以建成幾棵相異之二元樹

Input: 3
Output: 5
Explanation:
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

n = 2,there are a total of 2 unique BST's
  1        2
   \      /
   2     1

n = 3,there are a total of 5 unique BST's

分為三種case
1.
   1         1
    \         \
     3         2
    /           \
   2             3
2.
   2
  / \
 1   3
3.
  3      3
 /      /
1      2
 \    /
  2  1 

1. (ROOT後依序重複上面的case1 2 3)
    1        1            1            1        1 
     \        \            \            \        \
     2         2            3            4        4
      \         \          / \          /        /
       4         3        2   4        2        3
      /           \                     \      / 
     3             4                     3    2

2.
    2            2
   / \          / \
  1   3        1   4
       \          /
        4        3
3.   
    3        3
   / \      / \
  1   4    2   4
   \      /
    2    1
4.
    4        4            4        4        4
   /        /            /        /        /
  1        1            2        3        3
   \        \          / \      /        /
    3        2        1   3    1        2
   /          \                 \      /
  2            3                 2    1

經過觀察 n = 1, n = 2, n = 3, n = 4 的例子後，可以看出用遞迴的觀念可以算出所求。

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1, 0);  //宣告n+1個空間，賦值為零
        dp[0] = dp[1] = 1;
        for(int i = 2; i <= n; i++) {   //這邊使用DP求解
            for(int j = 0; j < i; j++) {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }
        return dp[n];
    }
};