# LeetCode 96. Unique Binary Search Trees

https://leetcode.com/problems/unique-binary-search-trees/description/

## 題目大意

給定 `n` 個 node 可以決定幾種 BST ？

## 思考

這題就考你資結有沒有認真上課了
答案就是 [Catalan number](https://en.wikipedia.org/wiki/Catalan_number)：

$$
C_n = \frac{1}{n+1}\binom{2n}{n} \text{, for } n\ge 0
$$

### Algo 1

class Solution
{
public:
    int numTrees(int n)
    {
        return binom(2 * n, n) / (n + 1);
    }

private:
    long long binom(int n, int k)
    {
        long long ans = 1;

        if (k > n - k)
            k = n - k;

        for (int i = 1; i <= k; ++i)
        {
            ans = ans * (n - i + 1) / i;
        }

        return ans;
    }
};

### Algo 2

為啥答案會是 Catalan number？
我們可以看到 Catalan number 有遞迴關係式：

$$
C_0 = 1 \text{, } C_{n} = \sum\limits_{i=0}^{n-1}C_iC_{n-1-i} \text{, for }n\gt 0
$$

怎麼聯想到 BST 呢？

對於 `n` 個 node 的 BST ，我們可以不失一般性的假設其 root 之左子樹有 `i` 個 node 、右子樹有 `n-1-i` 個 node

唉，這不就是上面的遞迴關係式了嗎 😎

有了遞迴關係式，你就可以用 DP 了

class Solution
{
public:
    int numTrees(int n)
    {
        vector<int> dp(n + 1);
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; ++i)
        {
            for (int j = 0; j < i; ++j)
            {
                dp[i] += dp[j] * dp[i - j - 1];
            }
        }

        return dp.back();
    }
};