给定一个有序序列1…n，为了构建出一棵二叉搜索树，我们可以遍历每个数字i，将该数字作为树根，将1…(i-1)序列作为左子树，将(i+1)…n序列作为右子树。接着我们可以按照同样的方式递归构建左子树和右子树。在上述构建过程中由于根的值不同，因此我们能保证每棵二叉搜索树是唯一的。由此可见，原问题可以分解成规模较小的两个子问题，且子问题的解可以复用。因此我们可以想到用动态规划来解决这个问题。
题目要求是计算不同的二叉搜索树的个数。为此，我们可以定义两个函数：1. G(n)：长度为n的序列能构成的不同二叉搜索树的个数。2. F(i, n)：以i为根，序列长度为n的不同二叉搜索树个数(1<=i<=n)。可见，G(n)是我们求解需要的函数。我们将会看到，G(n)可以从F(i, n)得到，而F(i, n)又会递归地依赖于G(n)。首先，不同的二叉搜索树的总数G(n)是对遍历所有i(i<=i<=n)的F(i, n)之和。而对于边界情况，当序列长度为1（只有根）或者为0（空树）时，只有一种情况，即：G(0)=1, G(1)=1。
给定序列1…n，我们选择数字i作为根，则根为i的所有二叉搜索树的集合是左子树集合和右子树集合的笛卡尔积，对于笛卡尔积中每个元素，加上根结点后形成完整的二叉搜索树。举例，对于[1, 2, 3, 4, 5, 6, 7]这个序列，创建以3为根，长度为7的不同二叉搜索树，我们需要从左子序列[1, 2]构建左子树，从右子序列[4, 5, 6, 7]构建右子树，然后将它们组合。对于这个例子，不同二叉搜索树的个数为F(3, 7)，我们将[1, 2]构建不同左子树的数量表示为G(2)，从[4, 5, 6, 7]构建不同右子树的数量表示为G(4)，注意到G(n)和序列的内容无关，只和序列长度有关，于是，F(3, 7) = G(2)G(4)。因此我们可得F(i, n) = G(i-1)G(n-i)，将上述的两个公式结合，我们可以得到一个G(n)的递归表达式，G(n) = sum(G(i-1)G(n-i))。然后我们计算G(n)即可得到答案。
这个算法的时间复杂度是O（N^2），空间复杂度是O（N）。G(n)就是卡塔兰数，所以在数学上有更简单的方法计算它。用公式的算法可以使得时间复杂度变为O(n)，空间复杂度降为O(1)。
python:
class Solution:
def numTrees(self, n: int) -> int:
G = [0] * (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]