# 96 - Unique Binary Search Trees

這題還滿有趣的，因為我們都知道只有一個 node 就只有一種可能，兩個 node 只有兩種可能，所以可以用這兩個資訊當作初始狀態。

然後接下來我們看看 n=3 的例子，我們會發現其實可以透過分別讓 1, 2, 3 當作 root，然後看左右子樹分別有幾個 node，就可以依此算出不同 root 情況下會有幾種組合。比較要注意的就是某一邊的子樹只有 0 個 node 時，計算組合的方式會不太一樣。

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;
        dp.reserve(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 = comb + dp[left] * dp[right];
                else
                    comb = comb + dp[left] + dp[right];
            }

            dp[i] = comb;
        }

        return dp[n];
    }
};

// idea: if we kow the number of nodes, we can retrieve the number of trees

上面的實作有點冗長，其實可以用更少的程式碼來實作，詳細可以看一下[這篇討論](https://leetcode.com/problems/unique-binary-search-trees/discuss/31666/DP-Solution-in-6-lines-with-explanation.-F(i-n)-G(i-1)-*-G(n-i))。