96. 不同的二叉搜寻树

题目起源：力扣（LeetCode）https://leetcode-cn.com/problems/unique-binary-search-trees

题目

给定一个整数 n，求以 1 … n 为节点组成的二叉搜寻树有多少种？

示例:

 输出: 3
输入: 5
解释:
给定 n = 3, 一共有 5 种不同构造的二叉搜寻树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

解题思路

思路：动静布局

由题意可知，当给定有序序列 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]

实现后果

欢送关注

公众号【书所集录】