96. 不同的二叉搜索树(中)

• 题目
• 动态规划

题目

动态规划

• 由于 1,2...n 这个数列是递增的，所以我们从任意一个位置“提起”这课树，都满足二叉搜索树的这个条件：左边儿子数小于爸爸数，右边儿子数大于爸爸数。例如，我要用 [1,2,3,4,5,6] 构建。首先，提起 "2" 作为树根，[1]为左子树，[3,4,5,6] 为右子树，现在就变成了一个更小的问题：如何用 [3,4,5,6] 构建搜索树？满足动态规划的重叠子问题的条件。

class Solution:
    def numTrees(self, n: int) -> int:
        dp = [0] * (n + 1)  # 创建动态规划数组，dp[i]表示i个节点能够构成的二叉搜索树的数量
        dp[0] = 1  # 空树也算一种情况，所以初始化dp[0]为1
        dp[1] = 1  # 只有一个节点的情况下，只有一种构成二叉搜索树的方式
        
        for i in range(2, n + 1):  # 从2开始计算，直到n
            for j in range(i):  # 遍历j，j表示左子树的节点数量
                dp[i] += dp[j] * dp[i - j - 1]  #组合左右子树不同的可能性
        return dp[n]  # 返回dp数组的最后一个元素，即n个节点能够构成的二叉搜索树的数量