线性动态规划：不同的二叉搜索树 题目描述 给定一个整数 \( n \)，求恰由 \( n \) 个节点组成且节点值从 1 到 \( n \) 互不相同的二叉搜索树 (BST) 有多少种？返回满足题意的二叉搜索树的种数。 示例： 输入: \( n = 3 \) 输出: 5 解释: 对于 n=3，有以下5种结构不同的二叉搜索树： 1 1 2 3 3 \ \ / \ / / 2 3 1 3 2 1 \ / / 3 2 1 2 解题过程 这个问题可以通过动态规划来解决，关键是理解BST的性质和如何利用子问题。 定义状态 设 \( dp[ i] \) 表示由 \( i \) 个不同的节点（值从1到i）能构成的二叉搜索树的数量。我们最终要求的是 \( dp[ n ] \)。 理解BST结构性质 在BST中，对于任意一个节点作为根，其左子树的所有节点值都小于根，右子树的所有节点值都大于根。 假设我们有 \( n \) 个不同的数（例如1到n）。如果我们选择数字 \( j \) (1 ≤ j ≤ n) 作为根节点，那么： 左子树将由 \( j-1 \) 个比 \( j \) 小的数（即1到j-1）构成。 右子树将由 \( n-j \) 个比 \( j \) 大的数（即j+1到n）构成。 左子树和右子树的构造是相互独立的。 状态转移方程 对于 \( n \) 个节点，总的BST数量是所有可能的根节点情况之和。 当根节点为 \( j \) 时： 左子树是 \( j-1 \) 个节点构成的BST，有 \( dp[ j-1 ] \) 种。 右子树是 \( n-j \) 个节点构成的BST，有 \( dp[ n-j ] \) 种。 那么以 \( j \) 为根的BST总数为 \( dp[ j-1] \times dp[ n-j ] \) (左右子树的组合是笛卡尔积)。 因此，总的 \( dp[ n ] \) 是所有可能的 \( j \) 对应的乘积之和： \[ dp[ n] = \sum_ {j=1}^{n} dp[ j-1] \times dp[ n-j ] \] 注意：当子树节点数为0时，我们定义只有一种结构（空树），所以 \( dp[ 0 ] = 1 \)。 初始化 \( dp[ 0 ] = 1 \) （空树算一种BST） 我们也可以设 \( dp[ 1 ] = 1 \)，但可以通过递推计算出来。 计算顺序 由于计算 \( dp[ n] \) 需要所有 \( dp[ k] \) (k < n)，我们从小到大计算 \( dp[ i ] \)，从 i=0 到 n。 举例演算 (n=3) 初始化: \( dp[ 0 ] = 1 \) 计算 \( dp[ 1 ] \)： \[ dp[ 1] = \sum_ {j=1}^{1} dp[ 0] \times dp[ 0 ] = 1 \times 1 = 1 \] 计算 \( dp[ 2 ] \)： \[ \begin{aligned} dp[ 2] &= \sum_ {j=1}^{2} dp[ j-1] \times dp[ 2-j ] \\ &= (dp[ 0] \times dp[ 1]) + (dp[ 1] \times dp[ 0 ]) \\ &= (1 \times 1) + (1 \times 1) = 2 \end{aligned} \] 计算 \( dp[ 3 ] \)： \[ \begin{aligned} dp[ 3] &= \sum_ {j=1}^{3} dp[ j-1] \times dp[ 3-j ] \\ &= (dp[ 0] \times dp[ 2]) + (dp[ 1] \times dp[ 1]) + (dp[ 2] \times dp[ 0 ]) \\ &= (1 \times 2) + (1 \times 1) + (2 \times 1) = 2+1+2 = 5 \end{aligned} \] 结果与示例一致。 算法复杂度 时间复杂度：\( O(n^2) \)。需要两层循环，外层 i 从 1 到 n，内层 j 从 1 到 i 求和。 空间复杂度：\( O(n) \)，存储dp数组。 关键点 这个递推公式定义的数列在数学上被称为卡特兰数 (Catalan number)，其通项公式为 \( C_ n = \frac{1}{n+1} \binom{2n}{n} \)，但动态规划是计算它的高效方法之一。 核心思想是：利用BST的性质，将问题分解为规模更小的左子树和右子树的子问题，然后组合。 总结 这个题目展示了如何利用BST的排序性质，将“n个节点的BST计数”问题分解为“左子树计数”和“右子树计数”两个子问题的乘积和，从而构造出动态规划的状态转移方程。