# 96. Unique Binary Search Trees

[Link](https://leetcode.com/problems/unique-binary-search-trees/)

**Solution**

BST 的組成方式可依照以誰當root來分

當我們選擇i-th element當作root，那麼則會有 i-1 個element在左子樹， n-i個在右子樹\
以i-th element當root的所有組合數為左右子樹的可能數相乘，  dp\[i-1] \* dp\[n-i]\
所以就可以簡化成 dp\[n] += dp\[i-1] \* dp\[n-i] // for i = 1 -> n(表示選ith element當root), dp\[0] = 1, dp\[1] = 1

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