最优二叉搜索树（Optimal Binary Search Tree, OBST）问题
字数 6189 2025-12-13 22:34:05

最优二叉搜索树（Optimal Binary Search Tree, OBST）问题

让我们来详细讲解最优二叉搜索树这个经典的区间动态规划问题。这个问题是区间DP的一个典型应用，涉及决策顺序和最优子结构。

1. 问题描述

假设我们有一个有序的关键字序列 \(K_1 < K_2 < \dots < K_n\)，以及每个关键字对应的搜索概率 \(p_1, p_2, \dots, p_n\)（表示搜索该关键字的频率）。

同时，我们还有 \(n+1\) 个“虚拟键”（dummy keys），表示不在关键字集合中的值（即搜索失败的情况），记为 \(D_0, D_1, \dots, D_n\)。每个虚拟键也有对应的搜索概率（即搜索失败落在该区间的频率） \(q_0, q_1, \dots, q_n\)。其中：

  • \(D_0\) 表示所有小于 \(K_1\) 的值。
  • \(D_i\) 表示所有介于 \(K_i\) 和 \(K_{i+1}\) 之间的值（对于 \(1 \le i \le n-1\)）。
  • \(D_n\) 表示所有大于 \(K_n\) 的值。

我们需要构建一棵二叉搜索树（BST），使得总的期望搜索代价最小。期望搜索代价定义为：每次搜索的代价（即从根到目标节点的深度+1）乘以对应概率的总和。

输入：

  • 正整数 \(n\)。
  • 数组 \(p[1..n]\)，表示成功搜索概率。
  • 数组 \(q[0..n]\)，表示失败搜索概率。
  • 满足：\(\sum_{i=1}^n p_i + \sum_{j=0}^n q_j = 1\)。

输出：

  • 最小的期望搜索代价。

注意：树的形态不固定，我们需要选择哪个关键字作为根，以及左右子树的划分，使得期望代价最小。

2. 问题分析与形式化

对于一个给定的BST，期望搜索代价的计算公式为：

\[E = \sum_{i=1}^n (depth(K_i)+1) \cdot p_i + \sum_{j=0}^n (depth(D_j)+1) \cdot q_j \]

其中 \(depth(\cdot)\) 表示节点在树中的深度（根节点深度为0）。可以改写为：

\[E = \sum_{i=1}^n depth(K_i) \cdot p_i + \sum_{j=0}^n depth(D_j) \cdot q_j + \sum_{i=1}^n p_i + \sum_{j=0}^n q_j \]

由于概率总和为1，所以后两项之和为1。因此最小化 \(E\) 等价于最小化：

\[\sum_{i=1}^n depth(K_i) \cdot p_i + \sum_{j=0}^n depth(D_j) \cdot q_j \]

但通常我们直接计算带深度的完整和。

3. 动态规划思路

3.1 最优子结构

如果我们选择 \(K_r\) 作为根，那么：

  • 左子树包含关键字 \(K_1, \dots, K_{r-1}\) 以及虚拟键 \(D_0, \dots, D_{r-1}\)。
  • 右子树包含关键字 \(K_{r+1}, \dots, K_n\) 以及虚拟键 \(D_r, \dots, D_n\)。

则原树的期望代价 = 左子树的期望代价 + 右子树的期望代价 + 所有节点的概率和（因为根节点深度增加1，所有子树的节点在计算代价时深度都增加了1）。

3.2 DP状态定义

定义 \(dp[i][j]\) 表示：由关键字 \(K_i, K_{i+1}, \dots, K_j\) 构成的OBST的最小期望搜索代价（其中 \(1 \le i \le j \le n\)）。

但为了处理失败情况，我们实际上考虑的关键字子序列是从 i 到 j，对应的虚拟键范围是 \(q_{i-1}\) 到 \(q_j\)。更标准的定义是：

设 \(dp[i][j]\) 表示由关键字 \(K_i, \dots, K_j\) 构成的子树的最小期望代价，其中 \(0 \le i \le j \le n\)，但这里关键字编号从1到n，虚拟键编号从0到n。为了统一，我们定义：

\(dp[i][j]\) 表示由虚拟键 \(D_{i-1}\) 和 \(D_j\) 之间（即包含关键字 \(K_i, \dots, K_j\) 以及虚拟键 \(D_{i-1}, D_i, \dots, D_j\)）构成的子树的最小期望代价，其中 \(1 \le i \le j \le n\)。但这样定义边界处理复杂，更常见的是：

定义：
设 \(w(i, j)\) 表示关键字 \(K_i, \dots, K_j\) 以及虚拟键 \(D_{i-1}, \dots, D_j\) 的概率总和，即：

\[w(i, j) = \sum_{k=i}^j p_k + \sum_{k=i-1}^j q_k \]

状态：
\(e[i][j]\) 表示由关键字 \(K_i, \dots, K_j\) 构成的最优二叉搜索树的最小期望搜索代价（其中 \(1 \le i \le j \le n\)）。
同时，我们还需要一个额外的状态 \(e[i][i-1]\) 表示空树（只包含虚拟键 \(D_{i-1}\)）的期望代价。显然，空树的期望代价就是 \(q_{i-1}\)（因为只有虚拟键，深度为0，期望代价 = 深度+1 = 1，乘以概率 \(q_{i-1}\) 得到 \(q_{i-1}\)）。实际上，更精确地，空树的期望代价 = \(q_{i-1}\)（因为只有一个虚拟键节点，深度0，代价=1*概率）。

3.3 状态转移方程

假设我们选择 \(K_r\)（其中 \(i \le r \le j\)）作为根。则：

  • 左子树包含关键字 \(K_i, \dots, K_{r-1}\)，其最小期望代价为 \(e[i][r-1]\)。
  • 右子树包含关键字 \(K_{r+1}, \dots, K_j\)，其最小期望代价为 \(e[r+1][j]\)。
  • 当我们将左右子树连接到根节点时，左右子树中所有节点的深度都增加了1，因此期望代价增加了这些节点概率的总和，这个总和正好是 \(w(i, j) - p_r\) 吗？不完全是。

实际上，整个子树的期望代价 = 左子树代价 + 右子树代价 + 所有节点的概率和（因为每个节点的深度+1，代价增加自身的概率值）。而“所有节点的概率和”就是 \(w(i, j)\)（包括关键字和虚拟键）。

因此，如果根是 \(K_r\)，则：

\[\text{代价} = e[i][r-1] + e[r+1][j] + w(i, j) \]

其中：

  • \(e[i][r-1]\) 当 \(r = i\) 时，表示左子树为空，其代价 = \(q_{i-1}\)（即 \(e[i][i-1] = q_{i-1}\)）。
  • \(e[r+1][j]\) 当 \(r = j\) 时，表示右子树为空，其代价 = \(q_j\)（即 \(e[j+1][j] = q_j\)）。

为了统一，我们定义：
\(e[i][i-1] = q_{i-1}\) 对于 \(1 \le i \le n+1\)（其中 \(e[n+1][n] = q_n\)）。

转移方程：

\[e[i][j] = \min_{i \le r \le j} \{ e[i][r-1] + e[r+1][j] + w(i, j) \} \]

其中 \(w(i, j) = \sum_{k=i}^j p_k + \sum_{k=i-1}^j q_k\)。

最终答案：\(e[1][n]\)。

3.4 计算顺序

  • 首先计算所有长度为1的区间（即单个关键字），然后长度递增。
  • 需要预处理 \(w(i, j)\)，可以通过前缀和快速计算。

4. 算法步骤

  1. 输入 \(n, p[1..n], q[0..n]\)。
  2. 初始化 \(e[i][i-1] = q_{i-1}\) 对于 \(i = 1\) 到 \(n+1\)（实际上只需要 \(i=1\) 到 \(n\) 以及 \(e[n+1][n]\) 但通常我们用二维数组 \(e[1..n+1][0..n]\)，其中 \(e[i][i-1]\) 有效）。
  3. 预处理 \(w(i, j)\) 数组，或者用前缀和实时计算。
  4. 按区间长度 \(len = 1\) 到 \(n\) 遍历：
    • 对于每个起始点 \(i = 1\) 到 \(n-len+1\)：
      • 设 \(j = i + len - 1\)。
      • 初始化 \(e[i][j] = \infty\)。
      • 计算 \(w(i, j) = \sum_{k=i}^j p_k + \sum_{k=i-1}^j q_k\)（可以用前缀和 \(sum\_pq[i][j]\) 提前算好）。
      • 对于每个可能的根 \(r\) 从 \(i\) 到 \(j\)：
        • \(e[i][j] = \min( e[i][j], e[i][r-1] + e[r+1][j] + w(i, j) )\)。
  5. 输出 \(e[1][n]\)。

时间复杂度：\(O(n^3)\)，因为三重循环（区间长度、起点、根位置）。
空间复杂度：\(O(n^2)\)。

5. 示例演示

假设 \(n=3\)，概率如下（为了简单，概率值已放大，总和为1）：

  • \(p = [0.1, 0.2, 0.3]\)
  • \(q = [0.05, 0.1, 0.15, 0.2]\)

步骤：

  1. 初始化：

    • \(e[1][0] = q_0 = 0.05\)
    • \(e[2][1] = q_1 = 0.1\)
    • \(e[3][2] = q_2 = 0.15\)
    • \(e[4][3] = q_3 = 0.2\)（虚拟数组，实际下标到n+1）

  2. 计算长度1的区间（单个关键字）：

    • \(i=1, j=1\)：
      • \(w(1,1) = p_1 + q_0 + q_1 = 0.1 + 0.05 + 0.1 = 0.25\)
      • 根只能选 \(r=1\)：
        • \(e[1][1] = e[1][0] + e[2][1] + 0.25 = 0.05 + 0.1 + 0.25 = 0.4\)
    • \(i=2, j=2\)：
      • \(w(2,2) = p_2 + q_1 + q_2 = 0.2 + 0.1 + 0.15 = 0.45\)
      • \(e[2][2] = e[2][1] + e[3][2] + 0.45 = 0.1 + 0.15 + 0.45 = 0.7\)
    • \(i=3, j=3\)：
      • \(w(3,3) = p_3 + q_2 + q_3 = 0.3 + 0.15 + 0.2 = 0.65\)
      • \(e[3][3] = e[3][2] + e[4][3] + 0.65 = 0.15 + 0.2 + 0.65 = 1.0\)

  3. 计算长度2的区间：

    • \(i=1, j=2\)：
      • \(w(1,2) = p_1+p_2 + q_0+q_1+q_2 = 0.1+0.2 + 0.05+0.1+0.15 = 0.6\)
      • 根 r=1：\(e[1][0] + e[2][2] + 0.6 = 0.05 + 0.7 + 0.6 = 1.35\)
      • 根 r=2：\(e[1][1] + e[3][2] + 0.6 = 0.4 + 0.15 + 0.6 = 1.15\)
      • 取最小值：\(e[1][2] = 1.15\)
    • \(i=2, j=3\)：
      • \(w(2,3) = p_2+p_3 + q_1+q_2+q_3 = 0.2+0.3 + 0.1+0.15+0.2 = 0.95\)
      • 根 r=2：\(e[2][1] + e[3][3] + 0.95 = 0.1 + 1.0 + 0.95 = 2.05\)
      • 根 r=3：\(e[2][2] + e[4][3] + 0.95 = 0.7 + 0.2 + 0.95 = 1.85\)
      • 取最小值：\(e[2][3] = 1.85\)

  4. 计算长度3的区间（整个树）：

    • \(i=1, j=3\)：
      • \(w(1,3) = p_1+p_2+p_3 + q_0+q_1+q_2+q_3 = 0.6 + 0.5 = 1.1\)
      • 根 r=1：\(e[1][0] + e[2][3] + 1.1 = 0.05 + 1.85 + 1.1 = 3.0\)
      • 根 r=2：\(e[1][1] + e[3][3] + 1.1 = 0.4 + 1.0 + 1.1 = 2.5\)
      • 根 r=3：\(e[1][2] + e[4][3] + 1.1 = 1.15 + 0.2 + 1.1 = 2.45\)
      • 取最小值：\(e[1][3] = 2.45\)

最终答案：最小期望代价 = 2.45。

6. 优化

上述算法是 \(O(n^3)\)，但可以优化到 \(O(n^2)\) 利用最优二叉搜索树的性质（Knuth优化）：对于固定的 \(i, j\)，最优根 \(r\) 的位置 \(root[i][j]\) 满足单调性，即 \(root[i][j-1] \le root[i][j] \le root[i+1][j]\)。这样在枚举根时可以缩小范围，但本问题不要求必须掌握优化。

7. 总结

最优二叉搜索树问题是一个典型的区间DP，核心在于：

  • 定义状态 \(e[i][j]\) 为子问题的最小期望代价。
  • 转移时枚举根节点，将问题分解为左右子树，并加上所有节点的概率和（因为深度+1）。
  • 初始化空树（只有虚拟键）的代价为对应虚拟键的概率。

这个问题的难点在于理解“期望代价”的递推公式，以及正确处理虚拟键的概率。掌握了这个模型，就能解决许多类似的区间划分最优决策问题。

最优二叉搜索树（Optimal Binary Search Tree, OBST）问题 让我们来详细讲解 最优二叉搜索树 这个经典的区间动态规划问题。这个问题是区间DP的一个典型应用，涉及决策顺序和最优子结构。 1. 问题描述 假设我们有一个 有序 的关键字序列 \( K_ 1 < K_ 2 < \dots < K_ n \)，以及每个关键字对应的搜索概率 \( p_ 1, p_ 2, \dots, p_ n \)（表示搜索该关键字的频率）。 同时，我们还有 \( n+1 \) 个“虚拟键”（dummy keys），表示不在关键字集合中的值（即搜索失败的情况），记为 \( D_ 0, D_ 1, \dots, D_ n \)。每个虚拟键也有对应的搜索概率（即搜索失败落在该区间的频率） \( q_ 0, q_ 1, \dots, q_ n \)。其中： \( D_ 0 \) 表示所有小于 \( K_ 1 \) 的值。 \( D_ i \) 表示所有介于 \( K_ i \) 和 \( K_ {i+1} \) 之间的值（对于 \( 1 \le i \le n-1 \)）。 \( D_ n \) 表示所有大于 \( K_ n \) 的值。 我们需要构建一棵 二叉搜索树 （BST），使得 总的期望搜索代价最小 。期望搜索代价定义为：每次搜索的代价（即从根到目标节点的深度+1）乘以对应概率的总和。 输入 ： 正整数 \( n \)。 数组 \( p[ 1..n ] \)，表示成功搜索概率。 数组 \( q[ 0..n ] \)，表示失败搜索概率。 满足：\( \sum_ {i=1}^n p_ i + \sum_ {j=0}^n q_ j = 1 \)。 输出 ： 最小的期望搜索代价。 注意 ：树的形态不固定，我们需要选择哪个关键字作为根，以及左右子树的划分，使得期望代价最小。 2. 问题分析与形式化 对于一个给定的BST， 期望搜索代价 的计算公式为： \[ E = \sum_ {i=1}^n (depth(K_ i)+1) \cdot p_ i + \sum_ {j=0}^n (depth(D_ j)+1) \cdot q_ j \] 其中 \( depth(\cdot) \) 表示节点在树中的深度（根节点深度为0）。可以改写为： \[ E = \sum_ {i=1}^n depth(K_ i) \cdot p_ i + \sum_ {j=0}^n depth(D_ j) \cdot q_ j + \sum_ {i=1}^n p_ i + \sum_ {j=0}^n q_ j \] 由于概率总和为1，所以后两项之和为1。因此最小化 \( E \) 等价于最小化： \[ \sum_ {i=1}^n depth(K_ i) \cdot p_ i + \sum_ {j=0}^n depth(D_ j) \cdot q_ j \] 但通常我们直接计算带深度的完整和。 3. 动态规划思路 3.1 最优子结构 如果我们选择 \( K_ r \) 作为根，那么： 左子树包含关键字 \( K_ 1, \dots, K_ {r-1} \) 以及虚拟键 \( D_ 0, \dots, D_ {r-1} \)。 右子树包含关键字 \( K_ {r+1}, \dots, K_ n \) 以及虚拟键 \( D_ r, \dots, D_ n \)。 则原树的期望代价 = 左子树的期望代价 + 右子树的期望代价 + 所有节点的概率和（因为根节点深度增加1，所有子树的节点在计算代价时深度都增加了1）。 3.2 DP状态定义 定义 \( dp[ i][ j] \) 表示： 由关键字 \( K_ i, K_ {i+1}, \dots, K_ j \) 构成的OBST的最小期望搜索代价 （其中 \( 1 \le i \le j \le n \)）。 但为了处理失败情况，我们实际上考虑的关键字子序列是从 i 到 j，对应的虚拟键范围是 \( q_ {i-1} \) 到 \( q_ j \)。更标准的定义是： 设 \( dp[ i][ j] \) 表示由关键字 \( K_ i, \dots, K_ j \) 构成的 子树 的最小期望代价，其中 \( 0 \le i \le j \le n \)，但这里关键字编号从1到n，虚拟键编号从0到n。为了统一，我们定义： \( dp[ i][ j] \) 表示由虚拟键 \( D_ {i-1} \) 和 \( D_ j \) 之间（即包含关键字 \( K_ i, \dots, K_ j \) 以及虚拟键 \( D_ {i-1}, D_ i, \dots, D_ j \)）构成的子树的最小期望代价，其中 \( 1 \le i \le j \le n \)。但这样定义边界处理复杂，更常见的是： 定义 ： 设 \( w(i, j) \) 表示关键字 \( K_ i, \dots, K_ j \) 以及虚拟键 \( D_ {i-1}, \dots, D_ j \) 的概率总和，即： \[ w(i, j) = \sum_ {k=i}^j p_ k + \sum_ {k=i-1}^j q_ k \] 状态 ： \( e[ i][ j] \) 表示由关键字 \( K_ i, \dots, K_ j \) 构成的 最优二叉搜索树 的最小期望搜索代价（其中 \( 1 \le i \le j \le n \)）。 同时，我们还需要一个额外的状态 \( e[ i][ i-1] \) 表示 空树 （只包含虚拟键 \( D_ {i-1} \)）的期望代价。显然，空树的期望代价就是 \( q_ {i-1} \)（因为只有虚拟键，深度为0，期望代价 = 深度+1 = 1，乘以概率 \( q_ {i-1} \) 得到 \( q_ {i-1} \)）。实际上，更精确地，空树的期望代价 = \( q_ {i-1} \)（因为只有一个虚拟键节点，深度0，代价=1* 概率）。 3.3 状态转移方程 假设我们选择 \( K_ r \)（其中 \( i \le r \le j \)）作为根。则： 左子树包含关键字 \( K_ i, \dots, K_ {r-1} \)，其最小期望代价为 \( e[ i][ r-1 ] \)。 右子树包含关键字 \( K_ {r+1}, \dots, K_ j \)，其最小期望代价为 \( e[ r+1][ j ] \)。 当我们将左右子树连接到根节点时， 左右子树中所有节点的深度都增加了1 ，因此期望代价增加了这些节点概率的总和，这个总和正好是 \( w(i, j) - p_ r \) 吗？不完全是。 实际上，整个子树的期望代价 = 左子树代价 + 右子树代价 + 所有节点的概率和（因为每个节点的深度+1，代价增加自身的概率值）。而“所有节点的概率和”就是 \( w(i, j) \)（包括关键字和虚拟键）。 因此，如果根是 \( K_ r \)，则： \[ \text{代价} = e[ i][ r-1] + e[ r+1][ j ] + w(i, j) \] 其中： \( e[ i][ r-1] \) 当 \( r = i \) 时，表示左子树为空，其代价 = \( q_ {i-1} \)（即 \( e[ i][ i-1] = q_ {i-1} \)）。 \( e[ r+1][ j] \) 当 \( r = j \) 时，表示右子树为空，其代价 = \( q_ j \)（即 \( e[ j+1][ j] = q_ j \)）。 为了统一，我们定义： \( e[ i][ i-1] = q_ {i-1} \) 对于 \( 1 \le i \le n+1 \)（其中 \( e[ n+1][ n] = q_ n \)）。 转移方程 ： \[ e[ i][ j] = \min_ {i \le r \le j} \{ e[ i][ r-1] + e[ r+1][ j ] + w(i, j) \} \] 其中 \( w(i, j) = \sum_ {k=i}^j p_ k + \sum_ {k=i-1}^j q_ k \)。 最终答案 ：\( e[ 1][ n ] \)。 3.4 计算顺序 首先计算所有长度为1的区间（即单个关键字），然后长度递增。 需要预处理 \( w(i, j) \)，可以通过前缀和快速计算。 4. 算法步骤 输入 \( n, p[ 1..n], q[ 0..n ] \)。 初始化 \( e[ i][ i-1] = q_ {i-1} \) 对于 \( i = 1 \) 到 \( n+1 \)（实际上只需要 \( i=1 \) 到 \( n \) 以及 \( e[ n+1][ n] \) 但通常我们用二维数组 \( e[ 1..n+1][ 0..n] \)，其中 \( e[ i][ i-1 ] \) 有效）。 预处理 \( w(i, j) \) 数组，或者用前缀和实时计算。 按区间长度 \( len = 1 \) 到 \( n \) 遍历： 对于每个起始点 \( i = 1 \) 到 \( n-len+1 \)： 设 \( j = i + len - 1 \)。 初始化 \( e[ i][ j ] = \infty \)。 计算 \( w(i, j) = \sum_ {k=i}^j p_ k + \sum_ {k=i-1}^j q_ k \)（可以用前缀和 \( sum\_pq[ i][ j ] \) 提前算好）。 对于每个可能的根 \( r \) 从 \( i \) 到 \( j \)： \( e[ i][ j] = \min( e[ i][ j], e[ i][ r-1] + e[ r+1][ j ] + w(i, j) ) \)。 输出 \( e[ 1][ n ] \)。 时间复杂度 ：\( O(n^3) \)，因为三重循环（区间长度、起点、根位置）。 空间复杂度 ：\( O(n^2) \)。 5. 示例演示 假设 \( n=3 \)，概率如下（为了简单，概率值已放大，总和为1）： \( p = [ 0.1, 0.2, 0.3 ] \) \( q = [ 0.05, 0.1, 0.15, 0.2 ] \) 步骤 ： 初始化： \( e[ 1][ 0] = q_ 0 = 0.05 \) \( e[ 2][ 1] = q_ 1 = 0.1 \) \( e[ 3][ 2] = q_ 2 = 0.15 \) \( e[ 4][ 3] = q_ 3 = 0.2 \)（虚拟数组，实际下标到n+1） 计算长度1的区间（单个关键字）： \( i=1, j=1 \)： \( w(1,1) = p_ 1 + q_ 0 + q_ 1 = 0.1 + 0.05 + 0.1 = 0.25 \) 根只能选 \( r=1 \)： \( e[ 1][ 1] = e[ 1][ 0] + e[ 2][ 1 ] + 0.25 = 0.05 + 0.1 + 0.25 = 0.4 \) \( i=2, j=2 \)： \( w(2,2) = p_ 2 + q_ 1 + q_ 2 = 0.2 + 0.1 + 0.15 = 0.45 \) \( e[ 2][ 2] = e[ 2][ 1] + e[ 3][ 2 ] + 0.45 = 0.1 + 0.15 + 0.45 = 0.7 \) \( i=3, j=3 \)： \( w(3,3) = p_ 3 + q_ 2 + q_ 3 = 0.3 + 0.15 + 0.2 = 0.65 \) \( e[ 3][ 3] = e[ 3][ 2] + e[ 4][ 3 ] + 0.65 = 0.15 + 0.2 + 0.65 = 1.0 \) 计算长度2的区间： \( i=1, j=2 \)： \( w(1,2) = p_ 1+p_ 2 + q_ 0+q_ 1+q_ 2 = 0.1+0.2 + 0.05+0.1+0.15 = 0.6 \) 根 r=1：\( e[ 1][ 0] + e[ 2][ 2 ] + 0.6 = 0.05 + 0.7 + 0.6 = 1.35 \) 根 r=2：\( e[ 1][ 1] + e[ 3][ 2 ] + 0.6 = 0.4 + 0.15 + 0.6 = 1.15 \) 取最小值：\( e[ 1][ 2 ] = 1.15 \) \( i=2, j=3 \)： \( w(2,3) = p_ 2+p_ 3 + q_ 1+q_ 2+q_ 3 = 0.2+0.3 + 0.1+0.15+0.2 = 0.95 \) 根 r=2：\( e[ 2][ 1] + e[ 3][ 3 ] + 0.95 = 0.1 + 1.0 + 0.95 = 2.05 \) 根 r=3：\( e[ 2][ 2] + e[ 4][ 3 ] + 0.95 = 0.7 + 0.2 + 0.95 = 1.85 \) 取最小值：\( e[ 2][ 3 ] = 1.85 \) 计算长度3的区间（整个树）： \( i=1, j=3 \)： \( w(1,3) = p_ 1+p_ 2+p_ 3 + q_ 0+q_ 1+q_ 2+q_ 3 = 0.6 + 0.5 = 1.1 \) 根 r=1：\( e[ 1][ 0] + e[ 2][ 3 ] + 1.1 = 0.05 + 1.85 + 1.1 = 3.0 \) 根 r=2：\( e[ 1][ 1] + e[ 3][ 3 ] + 1.1 = 0.4 + 1.0 + 1.1 = 2.5 \) 根 r=3：\( e[ 1][ 2] + e[ 4][ 3 ] + 1.1 = 1.15 + 0.2 + 1.1 = 2.45 \) 取最小值：\( e[ 1][ 3 ] = 2.45 \) 最终答案 ：最小期望代价 = 2.45。 6. 优化 上述算法是 \( O(n^3) \)，但可以优化到 \( O(n^2) \) 利用 最优二叉搜索树的性质 （Knuth优化）：对于固定的 \( i, j \)，最优根 \( r \) 的位置 \( root[ i][ j] \) 满足单调性，即 \( root[ i][ j-1] \le root[ i][ j] \le root[ i+1][ j ] \)。这样在枚举根时可以缩小范围，但本问题不要求必须掌握优化。 7. 总结 最优二叉搜索树问题是一个典型的区间DP，核心在于： 定义状态 \( e[ i][ j ] \) 为子问题的最小期望代价。 转移时枚举根节点，将问题分解为左右子树，并加上所有节点的概率和（因为深度+1）。 初始化空树（只有虚拟键）的代价为对应虚拟键的概率。 这个问题的难点在于理解“期望代价”的递推公式，以及正确处理虚拟键的概率。掌握了这个模型，就能解决许多类似的区间划分最优决策问题。