问题：
给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3
思路：
本题可采用动态规划求解，问题可分解成规模较小的子问题问题是计算不同二叉搜索树的个数，为此，定义两个函数：
G
(
n
)
G(n)
G(n)： 长度为 n 的序列的不同二叉搜索树的个数
F
(
i
,
n
)
F(i, n)
F(i,n)： 以 i 为根的不同二叉搜索树的个数(
1
≤
i
≤
n
1 ≤ i ≤ n
1≤i≤n)这里的
G
(
n
)
G(n)
G(n)就是我们解决问题的函数
G
(
n
)
=
∑
i
=
1
n
F
(
i
,
n
)
(1)
G(n) = \displaystyle \sum^{n}_{i = 1}{F(i, n)} \tag {1}
G(n)=i=1∑nF(i,n)(1)对于边界情况，当序列长度为1（只有跟）或为0（空树）时，只有一种情况。即：
G
(
0
)
=
1
,
G
(
1
)
=
1
G(0) = 1, G(1) = 1
G(0)=1,G(1)=1接着，举例来说，
F
(
3
,
7
)
F(3, 7)
F(3,7)为以
3
3
3为根的不同二叉搜索树个数。为了以
3
3
3为根从
[
1
,
2
,
3
,
4
,
5
,
6
,
7
]
[1, 2, 3, 4, 5, 6, 7]
[1,2,3,4,5,6,7]构建二叉搜索树，我们需要从左子序列
[
1
,
2
]
[1, 2]
[1,2]构建左子树，从右子序列
[
4
,
5
,
6
,
7
]
[4, 5, 6, 7]
[4,5,6,7]构建右子树，然后将它们组合。巧妙之处在于，
[
1
,
2
]
[1, 2]
[1,2]构建不同左子树的数量表示为
G
(
2
)
G(2)
G(2)，
[
4
,
5
,
6
,
7
]
[4, 5, 6, 7]
[4,5,6,7]构建不同右子树的数量表示为
G
(
4
)
G(4)
G(4).于是
F
(
3
,
7
)
=
G
(
2
)
⋅
G
(
4
)
F(3, 7) = G(2) · G(4)
F(3,7)=G(2)⋅G(4)。概括一下：
F
(
i
,
n
)
=
G
(
i
−
1
)
⋅
G
(
n
−
i
)
(2)
F(i, n) = G(i - 1) · G(n - i) \tag {2}
F(i,n)=G(i−1)⋅G(n−i)(2)结合公式(1)、(2)，可以得到G(n)的递归表达公式：
G
(
n
)
=
∑
i
=
1
n
G
(
i
−
1
)
⋅
G
(
n
−
i
)
(3)
G(n) = \displaystyle \sum^{n}_{i = 1} {G(i - 1) · G(n - i)} \tag {3}
G(n)=i=1∑nG(i−1)⋅G(n−i)(3)为了计算函数结果，我们从小到大计算，因为
G
(
n
)
G(n)
G(n)的值依赖于
G
(
0
)
…
G
(
n
−
1
)
。
G(0) \dots G(n - 1)。
G(0)…G(n−1)。
Solution
class Solution(object):
def numTrees(self
, n
):
G
= [0 for _
in range(n
+ 1)]
G
[0], G
[1] = 1, 1
for i
in range(2, n
+ 1):
for j
in range(1, i
+ 1):
G
[i
] += G
[j
- 1] * G
[i
- j
]
return G
[n
]
本题来源：https://leetcode-cn.com/problems/unique-binary-search-trees/
