# 96 - Unique Binary Search Trees

解法一 - Dynamic programming

這題可以這樣思考：

1. 先考慮 n = 3 的 BSTs

2. 會發現 n = 3 的 BST 可以想成是由 1, 2, 3 分別當 root，再排列剩下的 node 變化出來的

3. 因為是 BST，所以決定 root 之後，就會知道左右子樹各會有幾個 node

   假設我們從 n 個 node 中，選出第 j 個 node 當作 root，那左子樹就有 j-1 個 node，右子樹有 n-j 個 node。

4. 因為已經知道左邊有 j-1 個 node，右邊有 n-j 個 node，所以如果已經知道 j-1 個 node 有幾種排法（定義成 COMB(j-1)），也知道 n-j 個 node 有幾種排法（定義成 COMB(n-j)），那在以 j 當作 root 的情況下，就有 COMB(j-1)*COMB(n-j) 種排法。

有了上面的思考模式，我們就可以寫出 DP 的解：

class Solution {
public:
    int numTrees(int n) {
        if(n == 0) return 0;
        else if(n == 1) return 1;
        else if(n == 2) return 2;

        vector<int> dp(n+1);
        dp[0] = 0;
        dp[1] = 1;
        dp[2] = 2;

        // calculate all dp value
        for(int i=3; i<=n; i++) {
            // enumerate all combinations
            int comb = 0;

            for(int j=1; j<=i; j++) {
                int left = j-1;
                int right = i-j;
                if(left != 0 && right != 0)
                    comb += dp[left] * dp[right];
                else
                    comb += dp[left] + dp[right];
            }

            dp[i] = comb;
        }

        return dp[n];
    }
};