> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/dynamic_programming_i/cartesian-product/unique-binary-search-trees.md).

# Unique Binary Search Trees

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

> Given n, how many structurally unique BST's (binary search trees) that store values 1...n?

## Thoughts

不会做。看到[https://discuss.leetcode.com/topic/8398/dp-solution-in-6-lines-with-explanation-f-i-n-g-i-1-g-n-i/2 解释的很好。](https://discuss.leetcode.com/topic/8398/dp-solution-in-6-lines-with-explanation-f-i-n-g-i-1-g-n-i/2)

让G(n)表示长度为n的数列能形成的unique binary tree的数目，注意这里的G不仅代表了\[1, ..., n], 而是任意\[i, ...., i+ n-1]的能组成的数目。因为\[1, ..., n]组成的bst和\[i,..., i+ n -1] 能构成的bst数目是一致的，认清这点 **非常重要** 。F(i, n)表示以i为root的前n个元素能形成的unique bin tree个数, 那么f\[i]\[n] = G(i-1) \* G(n-i), 分别对应了左子树和右子树可能的情况。又因为G(n) = f(1, n) + f(2, n) + ...+ f(n, n).

合并两个式子能得到G(n) = G(0) \* G(n-1) + G(1) \* G(n-2) ... + G(n-1)\*G(0).

## Code

```
class Solution {
    public int numTrees(int n) {
        int[] G = new int[n + 1];
        G[0] = 1;
        for (int i = 1; i <= n; i++) {
            for (int j = 0; j < i; j++) {
                G[i] += G[j] * G[i - j - 1];
            }
        }

        return G[n];
    }
}
```

## Analysis

时间复杂度为O(n^2).