LeetCode 96. 不同的二叉搜索树 | Python

思路：动态规划

由题意可知，当给定有序序列 1…n，构建二叉搜索树，结合示例，可以得出的方案是：在区间 [1 - n] 中，遍历每个数字 i，以这个数字为根，然后将 i 左边序列作为左子树， i 右边序列作为右子树。

现在我们假设，给定的 n 个节点中，存在能构成二叉搜索树的数量为 G(n)，设以 i 为根的二叉搜索树的数量为 f(i)。那么我们就可以得到以下的公式：

G(n) = f(1) + f(2) + ... + f(n-1) + f(n)

也就是说，当要求给定序列 1…n 能构成多少二叉搜索树，需要求得 f(i)，（1<=i<=n） 的数量，然后将结果累加。

前面说了，以 i 为根节点，那么i 左边序列将作为左子树， i 右边序列作为右子树。在这里，左子树的节点个数有 i-1，而右子树的节点个数有 n-i 个，那么此时：

f(i) = G(i-1) * G(n-i)

这里需要注意的，G(n) 这里的 n 表示的是个数，跟序列的内容并没有关系。所以，上面的可构成左子树，右子树的数量，则由它们的节点数决定。

现在将 f(i) 最上面的公式，得到：

G(n) = G(0) * G(n-1) + G(1) * G(n-2) + ... + G(n-2) * G(1) + G(n-1) * G(0)

其实，这个其实就是卡塔兰数，有兴趣的话，可以了解一下（按个人条件，下方链接均可了解关于卡塔兰数具体的信息）。

https://en.wikipedia.org/wiki/Catalan_number(同上，源自：维基百科)

https://baike.baidu.com/item/catalan（源自：百度百科）

初始化

在这里，要注意边界问题：

• 当 n = 0 时，这里表示为空树，只有一种情况，所以 G(0) = 1；
• 当 n = 1 时，表示只有一个根，这里也只有一种情况，此时 G(1) = 1。

本题具体的代码实现如下。

class Solution:
    def numTrees(self, n: int) -> int:
 dp = [0] * (n + 1)

 # 初始化
 dp[0] = 1
 dp[1] = 1

 for i in range(2, n+1):
     for j in range(i+1):
  # 代入公式
  # 注意，这里是累加
  dp[i] += dp[j-1] * dp[i-j]

 return dp[-1]