> For the complete documentation index, see [llms.txt](https://851958789.gitbook.io/notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://851958789.gitbook.io/notes/0096_unique_binary_search_trees/slt.md).

# 思路1 dp

`G(n)`表示输入n时，能构建多少棵不同的BST。两个特殊情况是n=0和n=1时，空树和一个节点的树都只有一种情况，所以`G(0)=1, G(1)=1`

`F(i, n)`表示以i为根结点，n的序列能构建多少棵不同的BST。我们可以得到

`G(n) = F(1, n) + F(2, n) + ... + F(n, n)`

而`F(i, n)`又可以分成左右子树情况种类的乘积，即

`F(i, n) = G(i-1) * G(n-i), 1 <= i <= n`

最后可以得到

`G(n) = G(0) * G(n-1) + G(1) * G(n-2) + … + G(n-1) * G(0)`

最后计算的时候，要从小开始算