# 96. Unique Binary Search Trees
##### link : https://leetcode.com/problems/unique-binary-search-trees/description/
###### tags: `dp`

sources:
> https://ithelp.ithome.com.tw/articles/10213289
> https://blog.csdn.net/oNever_say_love/article/details/49420631
> https://johnmayhk.wordpress.com/2014/02/03/cn/

#### 這題的結果符合<font color="ff123">卡塔蘭數列</font>，以下為推導過程:

* 當 $n=0,1$ 時只會有一種二元樹，$DP[0]=1$ , $DP[1]=1$
* $n=2$ 時，會有兩種，$DP[2]=2$
* $n=3$ 時，可分成以下情形：
1. 根節點的左邊有兩個節點，右邊沒有節點。
2. 根節點的左右各一個節點。
3. 根節點的右邊有兩個節點，左邊則無。
#### 第一種情形可以看做根節點的左邊是一顆兩個節點的二元樹所有的組合數，右邊則是一個沒有節點的樹所有的組合數 => $DP[2]\times DP[0]$
#### 其他情形類推，得總方法數= $DP[2]\times DP[0]+DP[1]\times DP[1]+DP[0]\times DP[2]$

* 對於任何 n，都可以用這個規律類推: $f(0) \times f(n-1) + f(1) \times f(n-2) + … + f(n-1) \times f(0)$

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

        vector<int> dp(n+1,0);
        dp[1]=1;
        dp[0]=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[n];
    }
};