> For the complete documentation index, see [llms.txt](https://r24zeng.gitbook.io/leetcode-notebook/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://r24zeng.gitbook.io/leetcode-notebook/binary-search-and-tree/96.-unique-binary-search-trees.md).

# 96. Unique Binary Search Trees

\# Medium

{% hint style="info" %}
Dynamic Programming. Build `dp[n+1]` to record how many unique BST until `ith`. `dp[i]` = sum(dp\[smaller than root]\*dp\[greater than root]), `root` is changing.
{% endhint %}

![mums of trees = dp\[smaller than root\]\*dp\[greater than root\]](https://3288217904-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LxJcc9A1TOyn5a5HJQ4%2F-MANMN6JYTZCqaz_7T08%2F-MAP7Qkpv5DxF8pTJXeN%2F1592797537263.jpg?alt=media\&token=f6f99567-ff13-4d90-a0ca-67bc9f2c9402)

### Solution:

1. Initialize `dp[n+1]`, `dp[0]=1`. Think about how to compute `d[i]` and the value of `dp[1]` should be.
2. Move root until `ith`, sum all of the possible roots, then get `dp[i]`.
3. Return `dp[n]`

{% tabs %}
{% tab title="Python" %}

```python
class Solution:
    def numTrees(self, n: int) -> int:
        # initialize dp[i], dp[i] means number of trees until i
        dp = [1]*(n+1)
        
        # regular case
        for i in range(1, n+1):
            num = 0
            for j in range(1, i+1):
                root = j
                smaller = root-1
                greater = i-root
                num = num + dp[smaller]*dp[greater]
            dp[i] = num
            
        return dp[n]
                
```

{% endtab %}

{% tab title="Second Tab" %}

{% endtab %}
{% endtabs %}

Time complexity = $$O(n^2)$$ , space complexity = $$O(n)$$