线性动态规划：不同的二叉搜索树（Unique Binary Search Trees）

字数 2322 2025-12-14 11:59:45

线性动态规划：不同的二叉搜索树（Unique Binary Search Trees）

题目描述

给定一个整数 \(n\)，表示二叉搜索树（BST）中节点的值由 1 到 \(n\) 组成。要求计算能够生成的所有结构不同的二叉搜索树的数目。不同 BST 定义为结构不同，即树的形态不同（与节点具体值无关，因为 1 到 \(n\) 的 BST 结构唯一对应一种形态）。

示例：

输入：\(n = 3\)
输出：5
解释：对于节点值 1, 2, 3，可以生成以下 5 种结构不同的 BST：

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

解题步骤

1. 理解问题本质

二叉搜索树（BST）的定义是：左子树的所有节点值 < 根节点值 < 右子树的所有节点值。给定节点值 1 到 \(n\)，如果我们选择某个值 \(i\) 作为根节点，那么：

左子树将包含值 1 到 \(i-1\)（共 \(i-1\) 个节点）。
右子树将包含值 \(i+1\) 到 \(n\)（共 \(n-i\) 个节点）。

问题转化为：给定节点数量，计算不同结构的 BST 数量，且只与节点数量有关，与具体值无关（因为 BST 的结构只由节点排列顺序决定）。

2. 定义状态

设 \(G(n)\) 表示由 \(n\) 个不同节点（值 1 到 \(n\)）能生成的不同 BST 的数量。
更一般地，设 \(F(i, n)\) 表示以值 \(i\) 为根节点，节点总数为 \(n\) 的 BST 数量。但注意，由于 BST 结构只与节点数有关，我们可以简化：

以 \(i\) 为根时，左子树节点数为 \(i-1\)，右子树节点数为 \(n-i\)。
左子树的不同结构数 = \(G(i-1)\)（由 \(i-1\) 个节点生成的 BST 数量）。
右子树的不同结构数 = \(G(n-i)\)（由 \(n-i\) 个节点生成的 BST 数量，但这些节点的值实际上是 \(i+1\) 到 \(n\)，结构上与值 1 到 \(n-i\) 的 BST 相同）。

因此，以 \(i\) 为根的 BST 数量 = \(G(i-1) \times G(n-i)\)。

3. 推导递推关系

遍历所有可能的根节点 \(i\)（从 1 到 \(n\)），将每种情况的数量累加：

\[G(n) = \sum_{i=1}^{n} G(i-1) \times G(n-i) \]

其中，边界条件：

\(G(0) = 1\)：空树算一种结构（即左/右子树为空的情况）。
\(G(1) = 1\)：单个节点只有一种结构。

4. 动态规划计算过程

从 \(n = 0\) 开始，逐步计算 \(G(1), G(2), \dots, G(n)\)。

以 \(n = 3\) 为例：

初始化 \(G(0) = 1, G(1) = 1\)。
计算 \(G(2)\)：
- 根节点为 1：左子树节点数 0，右子树节点数 1 → \(G(0) \times G(1) = 1 \times 1 = 1\)。
- 根节点为 2：左子树节点数 1，右子树节点数 0 → \(G(1) \times G(0) = 1 \times 1 = 1\)。
- 总和：\(G(2) = 1 + 1 = 2\)。
计算 \(G(3)\)：
- 根节点为 1：左子树节点数 0，右子树节点数 2 → \(G(0) \times G(2) = 1 \times 2 = 2\)。
- 根节点为 2：左子树节点数 1，右子树节点数 1 → \(G(1) \times G(1) = 1 \times 1 = 1\)。
- 根节点为 3：左子树节点数 2，右子树节点数 0 → \(G(2) \times G(0) = 2 \times 1 = 2\)。
- 总和：\(G(3) = 2 + 1 + 2 = 5\)。

结果与示例一致。

5. 算法实现

我们可以用一维数组 dp 保存 \(G(k)\) 的值，dp[0] = 1。
外层循环 k = 1 to n，内层循环 i = 1 to k，累加 dp[i-1] * dp[k-i]。

时间复杂度：\(O(n^2)\)（双重循环）。
空间复杂度：\(O(n)\)（存储 dp 数组）。

6. 示例完整计算表（\(n = 4\)）

\(G(0) = 1\)
\(G(1) = 1\)
\(G(2) = G(0)G(1) + G(1)G(0) = 2\)
\(G(3) = G(0)G(2) + G(1)G(1) + G(2)G(0) = 2 + 1 + 2 = 5\)
\(G(4) = G(0)G(3) + G(1)G(2) + G(2)G(1) + G(3)G(0) = 5 + 2 + 2 + 5 = 14\)

因此，\(n = 4\) 时答案为 14。

关键点

该递推公式定义的 \(G(n)\) 实际上是卡特兰数（Catalan Number）：\(G(n) = \frac{1}{n+1} \binom{2n}{n}\)。
动态规划避免重复计算子问题，例如计算 \(G(4)\) 时直接使用已算出的 \(G(0), G(1), G(2), G(3)\)。
理解 BST 的结构仅依赖于节点数，是问题简化的核心。

通过以上步骤，我们系统地解决了“不同的二叉搜索树”计数问题。

线性动态规划：不同的二叉搜索树（Unique Binary Search Trees）题目描述给定一个整数 \( n \)，表示二叉搜索树（BST）中节点的值由 1 到 \( n \) 组成。要求计算能够生成的所有结构不同的二叉搜索树的数目。不同 BST 定义为结构不同，即树的形态不同（与节点具体值无关，因为 1 到 \( n \) 的 BST 结构唯一对应一种形态）。示例：输入：\( n = 3 \) 输出：5 解释：对于节点值 1, 2, 3，可以生成以下 5 种结构不同的 BST：解题步骤 1. 理解问题本质二叉搜索树（BST）的定义是：左子树的所有节点值 < 根节点值 < 右子树的所有节点值。给定节点值 1 到 \( n \)，如果我们选择某个值 \( i \) 作为根节点，那么：左子树将包含值 1 到 \( i-1 \)（共 \( i-1 \) 个节点）。右子树将包含值 \( i+1 \) 到 \( n \)（共 \( n-i \) 个节点）。问题转化为：给定节点数量，计算不同结构的 BST 数量，且只与节点数量有关，与具体值无关（因为 BST 的结构只由节点排列顺序决定）。 2. 定义状态设 \( G(n) \) 表示由 \( n \) 个不同节点（值 1 到 \( n \)）能生成的不同 BST 的数量。更一般地，设 \( F(i, n) \) 表示以值 \( i \) 为根节点，节点总数为 \( n \) 的 BST 数量。但注意，由于 BST 结构只与节点数有关，我们可以简化：以 \( i \) 为根时，左子树节点数为 \( i-1 \)，右子树节点数为 \( n-i \)。左子树的不同结构数 = \( G(i-1) \)（由 \( i-1 \) 个节点生成的 BST 数量）。右子树的不同结构数 = \( G(n-i) \)（由 \( n-i \) 个节点生成的 BST 数量，但这些节点的值实际上是 \( i+1 \) 到 \( n \)，结构上与值 1 到 \( n-i \) 的 BST 相同）。因此，以 \( i \) 为根的 BST 数量 = \( G(i-1) \times G(n-i) \)。 3. 推导递推关系遍历所有可能的根节点 \( i \)（从 1 到 \( n \)），将每种情况的数量累加： \[ G(n) = \sum_ {i=1}^{n} G(i-1) \times G(n-i) \] 其中，边界条件： \( G(0) = 1 \)：空树算一种结构（即左/右子树为空的情况）。 \( G(1) = 1 \)：单个节点只有一种结构。 4. 动态规划计算过程从 \( n = 0 \) 开始，逐步计算 \( G(1), G(2), \dots, G(n) \)。以 \( n = 3 \) 为例：初始化 \( G(0) = 1, G(1) = 1 \)。计算 \( G(2) \)：根节点为 1：左子树节点数 0，右子树节点数 1 → \( G(0) \times G(1) = 1 \times 1 = 1 \)。根节点为 2：左子树节点数 1，右子树节点数 0 → \( G(1) \times G(0) = 1 \times 1 = 1 \)。总和：\( G(2) = 1 + 1 = 2 \)。计算 \( G(3) \)：根节点为 1：左子树节点数 0，右子树节点数 2 → \( G(0) \times G(2) = 1 \times 2 = 2 \)。根节点为 2：左子树节点数 1，右子树节点数 1 → \( G(1) \times G(1) = 1 \times 1 = 1 \)。根节点为 3：左子树节点数 2，右子树节点数 0 → \( G(2) \times G(0) = 2 \times 1 = 2 \)。总和：\( G(3) = 2 + 1 + 2 = 5 \)。结果与示例一致。 5. 算法实现我们可以用一维数组 dp 保存 \( G(k) \) 的值， dp[0] = 1 。外层循环 k = 1 to n ，内层循环 i = 1 to k ，累加 dp[i-1] * dp[k-i] 。时间复杂度：\( O(n^2) \)（双重循环）。空间复杂度：\( O(n) \)（存储 dp 数组）。 6. 示例完整计算表（\( n = 4 \)） \( G(0) = 1 \) \( G(1) = 1 \) \( G(2) = G(0)G(1) + G(1)G(0) = 2 \) \( G(3) = G(0)G(2) + G(1)G(1) + G(2)G(0) = 2 + 1 + 2 = 5 \) \( G(4) = G(0)G(3) + G(1)G(2) + G(2)G(1) + G(3)G(0) = 5 + 2 + 2 + 5 = 14 \) 因此，\( n = 4 \) 时答案为 14。关键点该递推公式定义的 \( G(n) \) 实际上是卡特兰数（Catalan Number）：\( G(n) = \frac{1}{n+1} \binom{2n}{n} \)。动态规划避免重复计算子问题，例如计算 \( G(4) \) 时直接使用已算出的 \( G(0), G(1), G(2), G(3) \)。理解 BST 的结构仅依赖于节点数，是问题简化的核心。通过以上步骤，我们系统地解决了“不同的二叉搜索树”计数问题。