我来给你讲解 LeetCode 第 96 题：不同的二叉搜索树（Unique Binary Search Trees）。

题目描述

给定一个整数 n，求以 1...n 为节点组成的二叉搜索树有多少种不同的结构？

示例：

输入: n = 3
输出: 5
解释: 当 n = 3 时，共有 5 种不同结构的二叉搜索树

解题思路

第一步：理解问题本质

二叉搜索树（BST）的特点是：

• 左子树的所有节点值 < 根节点值
• 右子树的所有节点值 > 根节点值

我们要计算的是：用数字 1 到 n 能构造出多少种不同结构的 BST。

第二步：寻找规律（从简单情况开始）

n = 0：空树，只有 1 种情况
n = 1：只有一个节点，只有 1 种情况
n = 2：

• 以 1 为根：右子树为 2
• 以 2 为根：左子树为 1
  共有 2 种情况

n = 3：我们来分析所有可能情况

第三步：关键思路 - 动态规划

发现一个重要规律：
当固定根节点值为 i 时：

• 左子树由 1...i-1 组成，有 G(i-1) 种可能
• 右子树由 i+1...n 组成，有 G(n-i) 种可能

其中 G(k) 表示 k 个节点能组成的 BST 数量。

第四步：建立递推公式

设 dp[i] 表示 i 个节点能组成的 BST 数量：

• dp[0] = 1（空树）
• dp[1] = 1

对于 dp[n]，我们遍历每个数字 i 作为根节点：

• 左子树：i-1 个节点 → dp[i-1] 种
• 右子树：n-i 个节点 → dp[n-i] 种
• 以 i 为根的 BST 数量 = dp[i-1] × dp[n-i]

所以递推公式为：

dp[n] = Σ(dp[i-1] × dp[n-i])，其中 i 从 1 到 n

第五步：计算过程演示

计算 dp[2]：

• i=1：dp[0]×dp[1] = 1×1 = 1
• i=2：dp[1]×dp[0] = 1×1 = 1
• dp[2] = 1 + 1 = 2

计算 dp[3]：

• i=1：dp[0]×dp[2] = 1×2 = 2
• i=2：dp[1]×dp[1] = 1×1 = 1
• i=3：dp[2]×dp[0] = 2×1 = 2
• dp[3] = 2 + 1 + 2 = 5

计算 dp[4]：

• i=1：dp[0]×dp[3] = 1×5 = 5
• i=2：dp[1]×dp[2] = 1×2 = 2
• i=3：dp[2]×dp[1] = 2×1 = 2
• i=4：dp[3]×dp[0] = 5×1 = 5
• dp[4] = 5 + 2 + 2 + 5 = 14

第六步：算法实现

def numTrees(n: int) -> int:
    dp = [0] * (n + 1)
    dp[0] = 1  # 空树
    
    for i in range(1, n + 1):
        for j in range(1, i + 1):
            # 以 j 为根节点
            dp[i] += dp[j - 1] * dp[i - j]
    
    return dp[n]

第七步：复杂度分析

• 时间复杂度：O(n²) - 双重循环
• 空间复杂度：O(n) - dp 数组

第八步：数学背景（扩展知识）

这个数列实际上是卡特兰数，有闭式解公式：

C(n) = (2n)! / ((n+1)! × n!)

对于这个问题就是求第 n 个卡特兰数。

这个问题的巧妙在于发现了 BST 数量只与节点个数有关，与具体数值无关，通过动态规划将大问题分解为小问题的乘积和。