区间动态规划例题：最优二叉搜索树的期望搜索代价最小化问题（进阶：带深度限制）
字数 5623 2025-12-10 17:39:59

区间动态规划例题：最优二叉搜索树的期望搜索代价最小化问题（进阶：带深度限制）

题目描述
给定一棵二叉搜索树（BST）的 n 个不同关键字的集合，关键字按升序排列为 \(k_1 < k_2 < \dots < k_n\)，每个关键字 \(k_i\) 有一个被访问概率 \(p_i\)。此外，还定义了 n+1 个伪关键字（表示搜索值不在实际关键字中的情况），记作 \(d_0, d_1, \dots, d_n\)，其中 \(d_j\) 表示所有值在 \((k_j, k_{j+1})\) 区间内的搜索（约定 \(k_0 = -\infty, k_{n+1} = +\infty\)），每个 \(d_j\) 有一个被访问概率 \(q_j\)。
所有概率满足：

\[\sum_{i=1}^n p_i + \sum_{j=0}^n q_j = 1 \]

在 BST 中搜索一个值，其代价等于从根节点到该值对应节点的路径长度（即比较次数）。对于实际关键字 \(k_i\)，搜索代价等于其深度 +1（根节点深度为 0）；对于伪关键字 \(d_j\)，搜索代价等于其父节点（必为叶节点）的深度。
问题是：构造一棵 BST，使得期望搜索代价最小。
进阶约束：树的最大深度不得超过 D（即从根到最深层叶节点的比较次数 ≤ D+1）。求满足深度限制下的最小期望搜索代价。

解题过程

1. 基础问题回顾（不带深度限制）
设 \(e[i][j]\) 表示由关键字 \(k_i, \dots, k_j\) 构造的最优 BST 的期望搜索代价（其中 \(1 \le i \le j \le n\)）。
记 \(w[i][j]\) 为子树中所有关键字和伪关键字的概率和：

\[w[i][j] = \sum_{l=i}^j p_l + \sum_{l=i-1}^j q_l \]

基础状态转移方程：

\[e[i][j] = \min_{r=i}^{j} \{ e[i][r-1] + e[r+1][j] + w[i][j] \} \]

其中 \(r\) 为根节点关键字的下标。
初始化：当 \(i > j\) 时，子树为空，只包含伪关键字 \(d_{j}\)，有 \(e[i][j] = q_{j}\)（但通常处理为 \(e[i][i-1] = q_{i-1}\)）。
最终答案：\(e[1][n]\)。

2. 引入深度限制的挑战
深度限制意味着我们不能无限制地延伸树的深度。
直接想法：在状态中增加一维 \(d\) 表示当前子树的允许最大深度。
定义 \(f[i][j][d]\) 表示以关键字 \(k_i, \dots, k_j\) 构造的 BST，且从当前子树的根节点到其任何叶节点的最大深度不超过 d 的最小期望搜索代价。
这里“深度”是相对于当前子树的根而言的，即当前子树的根的深度为 0，其子节点的深度为 1，以此类推。
我们需要最终满足整棵树的根深度限制为 D。

3. 状态转移推导
选择 \(k_r\) 作为根，则左子树包含 \(k_i, \dots, k_{r-1}\)，右子树包含 \(k_{r+1}, \dots, k_j\)。
对于左子树，其根（即 \(k_r\) 的左子节点）的深度相对于当前子树根的深度是 1，因此左子树允许的最大深度变为 \(d-1\)。
类似地，右子树允许的最大深度也是 \(d-1\)。
期望代价的组成：

  • 左子树的期望代价：\(f[i][r-1][d-1]\)（注意：左子树可能为空）
  • 右子树的期望代价：\(f[r+1][j][d-1]\)
  • 加上当前子树所有结点的概率和 \(w[i][j]\)，因为根节点深度增加 1 会导致所有结点的搜索代价增加 1 次比较，而期望值的增量正好是概率和。

因此，转移方程为：

\[f[i][j][d] = \min_{r=i}^{j} \left\{ f[i][r-1][d-1] + f[r+1][j][d-1] + w[i][j] \right\} \]

其中 \(d \ge 0\)。

4. 边界情况处理

  • 当 \(i > j\) 时，子树为空，只对应一个伪关键字 \(d_j\)。此时，若 \(d \ge 0\)，该伪关键字作为叶节点，其深度为 0（相对于当前空子树的“根”），搜索代价为 0，但概率 \(q_j\) 仍需计入上层。实际上，在 \(i > j\) 时，我们单独定义：

\[ g[i][j][d] = 0 \quad \text{（空子树的期望代价为0，但概率累加在父节点的 w 中）} \]

更一致的做法是：在 \(i > j\) 时，\(f[i][j][d] = 0\) 对任意 \(d \ge 0\)，而概率 \(q_j\) 已包含在父树的 \(w\) 中。
但注意：在 \(i = j+1\) 时，区间为空，伪关键字是 \(d_j\)，在父树计算时，\(w[i][j]\) 中已包含 \(q_j\)。
因此我们可以统一用 \(f[i][j][d]\) 表示区间 \([i,j]\) 的子树代价，当 \(i > j\) 时 \(f = 0\)。

  • 当 \(d = 0\) 时，表示子树深度不能超过 0，即子树只能是一个叶节点（伪关键字）。但若区间 \([i,j]\) 非空（即包含实际关键字），则不可能构造出深度 0 的 BST，因为至少有一个关键字的深度为 0（根），深度为 0 意味着没有子节点，但此时该关键字是唯一的实际关键字，它的伪关键字子女深度为 1，超过限制。
    实际上，当 \(d = 0\) 且 \(i \le j\) 时，我们应设置 \(f[i][j][0] = +\infty\) 表示不可行。
    但更精确的处理是：深度 d 表示从当前子树的根到叶的最大深度，若 d=0，则根必须是叶节点，但实际关键字不能是叶节点（因为叶节点是伪关键字）。
    因此，对于非空区间 (\(i \le j\))，合法的 d 至少为 1。
    我们规定：叶节点（伪关键字）的深度为 0，那么一个实际关键字的深度至少为 0，其左右两个伪关键字深度为 1。
    为了避免混淆，定义 d 为“当前子树中从根到叶的路径上的节点数”（即比较次数），则 d ≥ 1。
    但为了与常见文献一致，我们调整定义：

    重新定义：
    设 \(dp[i][j][h]\) 表示以 \(k_i,\dots,k_j\) 构造的子树，且该子树的高度（从根到最远叶节点的边数）不超过 h 的最小期望代价。
    此时高度 h ≥ 0，h=0 表示子树只有一个伪关键字叶节点（但这种情况只在 i>j 时发生）。
    对于 i ≤ j 的子树，高度至少为 1（根是实际关键字，其两个伪关键字子女深度为 1）。

    转移：根为 \(k_r\)，左子树高度 ≤ h-1，右子树高度 ≤ h-1，于是：

\[ dp[i][j][h] = \min_{r=i}^{j} \left\{ dp[i][r-1][h-1] + dp[r+1][j][h-1] + w[i][j] \right\} \]

边界：

  • 当 i > j 时，子树为空，对应伪关键字 \(d_j\)，其高度为 0，期望代价即 \(q_j\) 乘深度 0 吗？不对，因为 \(q_j\) 的代价是它在父树中的深度。在空子树中，代价为 0，概率计入父树的 w 中。所以：

\[ dp[i][j][h] = 0 \quad \forall h \ge 0, \text{ 当 } i > j \]

  • 当 i ≤ j 且 h = 0 时，不可能构造（因为至少需要一个实际关键字，高度至少为1），设 \(dp[i][j][0] = +\infty\)。

最终答案：\(dp[1][n][D]\)，其中 D 是整棵树允许的最大高度。

5. 算法步骤细化
输入：关键字概率 p[1..n]，伪关键字概率 q[0..n]，高度限制 D。
步骤：

  1. 计算前缀概率和，以便快速计算 \(w[i][j]\)：

\[ w[i][j] = (sp[j] - sp[i-1]) + (sq[j] - sq[i-2]) \]

其中 \(sp[t] = \sum_{l=1}^t p_l\)，\(sq[t] = \sum_{l=0}^t q_l\)（设 sq[-1]=0）。
更直接地，预处理：

\[ w[i][j] = \sum_{l=i}^j p_l + \sum_{l=i-1}^j q_l \]

可 O(n²) 预先算出或每次 O(1) 用前缀和计算。

  1. 初始化 dp 数组为无穷大，维度 [n+2][n+2][D+1]（索引从 1 到 n，空区间用 i>j 表示）。
  2. 对每个区间长度 len = 0 到 n-1：
    • 对每个 i = 1 到 n-len：
      • j = i+len
      • 对每个高度 h = 1 到 D：
        • 先处理空子树：若 i>j 则 dp[i][j][h]=0，但 i>j 实际上只在 r=i 或 r=j 时作为子树出现，我们可以单独在转移中处理。
          实际上，我们可以初始化所有 i>j 的 dp[i][j][h]=0 对任意 h。
        • 对每个可能的根 r = i 到 j：
          • 左子树区间 [i, r-1]，右子树区间 [r+1, j]。
          • 如果 h=1，左右子树必须为空（因为高度不能超过0），即要求 r-1 < i 且 j < r+1，这只有 i=j 时可能。
            当 i=j 且 h=1，此时左子树 [i, r-1] 为空，右子树 [r+1, j] 为空，dp[i][i][1] = 0 + 0 + w[i][i]。
            解释：高度为1的子树只有一个实际关键字根，其两个伪关键字子女高度为0（已包含在空子树代价0中），总代价 = w[i][i]。
          • 若 h>1，则

\[ cost = dp[i][r-1][h-1] + dp[r+1][j][h-1] + w[i][j] \]

     - 用 cost 更新 dp[i][j][h] 的最小值。
  1. 最终答案 = min_{h=0..D} dp[1][n][h]（因为高度可以小于 D，取最小代价）。注意这里 h 从 0 开始，但 dp[1][n][0] 一定是无穷大（除非 n=0），所以实际上 h 从 1 开始。

6. 复杂度分析
状态数：O(n²D)
每个状态需要枚举根 r：O(n)
总时间复杂度 O(n³D)
空间复杂度 O(n²D)（可优化到 O(n²) 如果按 h 递增计算并只保留上一层 h-1 的结果，但需注意区间长度循环顺序）

7. 示例说明
设 n=2, p=[0.1,0.2], q=[0.05,0.1,0.15], D=2。
计算 w[1][1]=p1+q0+q1=0.1+0.05+0.1=0.25
w[2][2]=p2+q1+q2=0.2+0.1+0.15=0.45
w[1][2]=p1+p2+q0+q1+q2=0.3+0.3=0.6（检验：0.1+0.2+0.05+0.1+0.15=0.6）

初始化 dp[i][j][h]=inf，dp[i][i-1][h]=0。
h=1:
dp[1][1][1] = dp[1][0][0]+dp[2][1][0]+w[1][1] = 0+0+0.25=0.25
dp[2][2][1] = 0+0+0.45=0.45
dp[1][2][1]：需要根 r=1 或 2。
r=1: 左空 dp[1][0][0]=0，右 dp[2][2][0]=inf → 不可行
r=2: 左 dp[1][1][0]=inf，右空 → 不可行
所以 dp[1][2][1]=inf

h=2:
dp[1][1][2]: 根只能 r=1，左空右空，cost=0+0+0.25=0.25（同 h=1）
dp[2][2][2]=0.45
dp[1][2][2]:
r=1: 左空 dp[1][0][1]=0，右 dp[2][2][1]=0.45，cost=0+0.45+0.6=1.05
r=2: 左 dp[1][1][1]=0.25，右空=0，cost=0.25+0+0.6=0.85
取 min=0.85

最终答案 = min(dp[1][2][1],dp[1][2][2])=0.85，对应高度 2 的树。

8. 总结
本题是经典最优二叉搜索树问题的带深度限制扩展。关键点在于状态增加高度维度，转移时左右子树的高度上限减 1。需要注意空子树的处理（代价为 0，概率已计入父树的 w 中），以及高度为 0 时非空子树的不可行性。算法复杂度为 O(n³D)，可用于中等规模的 n 和 D。

区间动态规划例题：最优二叉搜索树的期望搜索代价最小化问题（进阶：带深度限制） 题目描述 给定一棵二叉搜索树（BST）的 n 个不同关键字的集合，关键字按升序排列为 \( k_ 1 < k_ 2 < \dots < k_ n \)，每个关键字 \( k_ i \) 有一个被访问概率 \( p_ i \)。此外，还定义了 n+1 个伪关键字（表示搜索值不在实际关键字中的情况），记作 \( d_ 0, d_ 1, \dots, d_ n \)，其中 \( d_ j \) 表示所有值在 \( (k_ j, k_ {j+1}) \) 区间内的搜索（约定 \( k_ 0 = -\infty, k_ {n+1} = +\infty \)），每个 \( d_ j \) 有一个被访问概率 \( q_ j \)。 所有概率满足： \[ \sum_ {i=1}^n p_ i + \sum_ {j=0}^n q_ j = 1 \] 在 BST 中搜索一个值，其代价等于从根节点到该值对应节点的路径长度（即比较次数）。对于实际关键字 \( k_ i \)，搜索代价等于其深度 +1（根节点深度为 0）；对于伪关键字 \( d_ j \)，搜索代价等于其父节点（必为叶节点）的深度。 问题是：构造一棵 BST，使得 期望搜索代价 最小。 进阶约束 ：树的 最大深度不得超过 D （即从根到最深层叶节点的比较次数 ≤ D+1）。求满足深度限制下的最小期望搜索代价。 解题过程 1. 基础问题回顾（不带深度限制） 设 \( e[ i][ j] \) 表示由关键字 \( k_ i, \dots, k_ j \) 构造的最优 BST 的期望搜索代价（其中 \( 1 \le i \le j \le n \)）。 记 \( w[ i][ j ] \) 为子树中所有关键字和伪关键字的概率和： \[ w[ i][ j] = \sum_ {l=i}^j p_ l + \sum_ {l=i-1}^j q_ l \] 基础状态转移方程： \[ e[ i][ j] = \min_ {r=i}^{j} \{ e[ i][ r-1] + e[ r+1][ j] + w[ i][ j ] \} \] 其中 \( r \) 为根节点关键字的下标。 初始化：当 \( i > j \) 时，子树为空，只包含伪关键字 \( d_ {j} \)，有 \( e[ i][ j] = q_ {j} \)（但通常处理为 \( e[ i][ i-1] = q_ {i-1} \)）。 最终答案：\( e[ 1][ n ] \)。 2. 引入深度限制的挑战 深度限制意味着我们不能无限制地延伸树的深度。 直接想法：在状态中增加一维 \( d \) 表示当前子树的 允许最大深度 。 定义 \( f[ i][ j][ d] \) 表示以关键字 \( k_ i, \dots, k_ j \) 构造的 BST，且 从当前子树的根节点到其任何叶节点的最大深度不超过 d 的最小期望搜索代价。 这里“深度”是相对于当前子树的根而言的，即当前子树的根的深度为 0，其子节点的深度为 1，以此类推。 我们需要最终满足整棵树的根深度限制为 D。 3. 状态转移推导 选择 \( k_ r \) 作为根，则左子树包含 \( k_ i, \dots, k_ {r-1} \)，右子树包含 \( k_ {r+1}, \dots, k_ j \)。 对于左子树，其根（即 \( k_ r \) 的左子节点）的深度相对于当前子树根的深度是 1，因此左子树允许的最大深度变为 \( d-1 \)。 类似地，右子树允许的最大深度也是 \( d-1 \)。 期望代价的组成： 左子树的期望代价：\( f[ i][ r-1][ d-1 ] \)（注意：左子树可能为空） 右子树的期望代价：\( f[ r+1][ j][ d-1 ] \) 加上当前子树所有结点的概率和 \( w[ i][ j ] \)，因为根节点深度增加 1 会导致所有结点的搜索代价增加 1 次比较，而期望值的增量正好是概率和。 因此，转移方程为： \[ f[ i][ j][ d] = \min_ {r=i}^{j} \left\{ f[ i][ r-1][ d-1] + f[ r+1][ j][ d-1] + w[ i][ j ] \right\} \] 其中 \( d \ge 0 \)。 4. 边界情况处理 当 \( i > j \) 时，子树为空，只对应一个伪关键字 \( d_ j \)。此时，若 \( d \ge 0 \)，该伪关键字作为叶节点，其深度为 0（相对于当前空子树的“根”），搜索代价为 0，但概率 \( q_ j \) 仍需计入上层。实际上，在 \( i > j \) 时，我们单独定义： \[ g[ i][ j][ d ] = 0 \quad \text{（空子树的期望代价为0，但概率累加在父节点的 w 中）} \] 更一致的做法是：在 \( i > j \) 时，\( f[ i][ j][ d] = 0 \) 对任意 \( d \ge 0 \)，而概率 \( q_ j \) 已包含在父树的 \( w \) 中。 但注意：在 \( i = j+1 \) 时，区间为空，伪关键字是 \( d_ j \)，在父树计算时，\( w[ i][ j] \) 中已包含 \( q_ j \)。 因此我们可以统一用 \( f[ i][ j][ d] \) 表示区间 \([ i,j ]\) 的子树代价，当 \( i > j \) 时 \( f = 0 \)。 当 \( d = 0 \) 时，表示子树深度不能超过 0，即子树只能是一个叶节点（伪关键字）。但若区间 \( [ i,j ] \) 非空（即包含实际关键字），则不可能构造出深度 0 的 BST，因为至少有一个关键字的深度为 0（根），深度为 0 意味着没有子节点，但此时该关键字是唯一的实际关键字，它的伪关键字子女深度为 1，超过限制。 实际上，当 \( d = 0 \) 且 \( i \le j \) 时，我们应设置 \( f[ i][ j][ 0 ] = +\infty \) 表示不可行。 但更精确的处理是：深度 d 表示 从当前子树的根到叶的最大深度 ，若 d=0，则根必须是叶节点，但实际关键字不能是叶节点（因为叶节点是伪关键字）。 因此，对于非空区间 (\( i \le j \))，合法的 d 至少为 1。 我们规定：叶节点（伪关键字）的深度为 0，那么一个实际关键字的深度至少为 0，其左右两个伪关键字深度为 1。 为了避免混淆，定义 d 为“当前子树中从根到叶的 路径上的节点数 ”（即比较次数），则 d ≥ 1。 但为了与常见文献一致，我们调整定义： 重新定义 ： 设 \( dp[ i][ j][ h] \) 表示以 \( k_ i,\dots,k_ j \) 构造的子树，且该子树的 高度 （从根到最远叶节点的边数）不超过 h 的最小期望代价。 此时高度 h ≥ 0，h=0 表示子树只有一个伪关键字叶节点（但这种情况只在 i>j 时发生）。 对于 i ≤ j 的子树，高度至少为 1（根是实际关键字，其两个伪关键字子女深度为 1）。 转移：根为 \( k_ r \)，左子树高度 ≤ h-1，右子树高度 ≤ h-1，于是： \[ dp[ i][ j][ h] = \min_ {r=i}^{j} \left\{ dp[ i][ r-1][ h-1] + dp[ r+1][ j][ h-1] + w[ i][ j ] \right\} \] 边界： 当 i > j 时，子树为空，对应伪关键字 \( d_ j \)，其高度为 0，期望代价即 \( q_ j \) 乘深度 0 吗？不对，因为 \( q_ j \) 的代价是它在父树中的深度。在空子树中，代价为 0，概率计入父树的 w 中。所以： \[ dp[ i][ j][ h ] = 0 \quad \forall h \ge 0, \text{ 当 } i > j \] 当 i ≤ j 且 h = 0 时，不可能构造（因为至少需要一个实际关键字，高度至少为1），设 \( dp[ i][ j][ 0 ] = +\infty \)。 最终答案：\( dp[ 1][ n][ D ] \)，其中 D 是整棵树允许的最大高度。 5. 算法步骤细化 输入：关键字概率 p[ 1..n]，伪关键字概率 q[ 0..n ]，高度限制 D。 步骤： 计算前缀概率和，以便快速计算 \( w[ i][ j ] \)： \[ w[ i][ j] = (sp[ j] - sp[ i-1]) + (sq[ j] - sq[ i-2 ]) \] 其中 \( sp[ t] = \sum_ {l=1}^t p_ l \)，\( sq[ t] = \sum_ {l=0}^t q_ l \)（设 sq[ -1 ]=0）。 更直接地，预处理： \[ w[ i][ j] = \sum_ {l=i}^j p_ l + \sum_ {l=i-1}^j q_ l \] 可 O(n²) 预先算出或每次 O(1) 用前缀和计算。 初始化 dp 数组为无穷大，维度 [ n+2][ n+2][ D+1 ]（索引从 1 到 n，空区间用 i>j 表示）。 对每个区间长度 len = 0 到 n-1： 对每个 i = 1 到 n-len： j = i+len 对每个高度 h = 1 到 D： 先处理空子树：若 i>j 则 dp[ i][ j][ h ]=0，但 i>j 实际上只在 r=i 或 r=j 时作为子树出现，我们可以单独在转移中处理。 实际上，我们可以初始化所有 i>j 的 dp[ i][ j][ h ]=0 对任意 h。 对每个可能的根 r = i 到 j： 左子树区间 [ i, r-1]，右子树区间 [ r+1, j ]。 如果 h=1，左右子树必须为空（因为高度不能超过0），即要求 r-1 < i 且 j < r+1，这只有 i=j 时可能。 当 i=j 且 h=1，此时左子树 [ i, r-1] 为空，右子树 [ r+1, j] 为空，dp[ i][ i][ 1] = 0 + 0 + w[ i][ i ]。 解释：高度为1的子树只有一个实际关键字根，其两个伪关键字子女高度为0（已包含在空子树代价0中），总代价 = w[ i][ i ]。 若 h>1，则 \[ cost = dp[ i][ r-1][ h-1] + dp[ r+1][ j][ h-1] + w[ i][ j ] \] 用 cost 更新 dp[ i][ j][ h ] 的最小值。 最终答案 = min_ {h=0..D} dp[ 1][ n][ h]（因为高度可以小于 D，取最小代价）。注意这里 h 从 0 开始，但 dp[ 1][ n][ 0 ] 一定是无穷大（除非 n=0），所以实际上 h 从 1 开始。 6. 复杂度分析 状态数：O(n²D) 每个状态需要枚举根 r：O(n) 总时间复杂度 O(n³D) 空间复杂度 O(n²D)（可优化到 O(n²) 如果按 h 递增计算并只保留上一层 h-1 的结果，但需注意区间长度循环顺序） 7. 示例说明 设 n=2, p=[ 0.1,0.2], q=[ 0.05,0.1,0.15 ], D=2。 计算 w[ 1][ 1 ]=p1+q0+q1=0.1+0.05+0.1=0.25 w[ 2][ 2 ]=p2+q1+q2=0.2+0.1+0.15=0.45 w[ 1][ 2 ]=p1+p2+q0+q1+q2=0.3+0.3=0.6（检验：0.1+0.2+0.05+0.1+0.15=0.6） 初始化 dp[ i][ j][ h]=inf，dp[ i][ i-1][ h ]=0。 h=1: dp[ 1][ 1][ 1] = dp[ 1][ 0][ 0]+dp[ 2][ 1][ 0]+w[ 1][ 1 ] = 0+0+0.25=0.25 dp[ 2][ 2][ 1 ] = 0+0+0.45=0.45 dp[ 1][ 2][ 1 ]：需要根 r=1 或 2。 r=1: 左空 dp[ 1][ 0][ 0]=0，右 dp[ 2][ 2][ 0 ]=inf → 不可行 r=2: 左 dp[ 1][ 1][ 0 ]=inf，右空 → 不可行 所以 dp[ 1][ 2][ 1 ]=inf h=2: dp[ 1][ 1][ 2 ]: 根只能 r=1，左空右空，cost=0+0+0.25=0.25（同 h=1） dp[ 2][ 2][ 2 ]=0.45 dp[ 1][ 2][ 2 ]: r=1: 左空 dp[ 1][ 0][ 1]=0，右 dp[ 2][ 2][ 1 ]=0.45，cost=0+0.45+0.6=1.05 r=2: 左 dp[ 1][ 1][ 1 ]=0.25，右空=0，cost=0.25+0+0.6=0.85 取 min=0.85 最终答案 = min(dp[ 1][ 2][ 1],dp[ 1][ 2][ 2 ])=0.85，对应高度 2 的树。 8. 总结 本题是经典最优二叉搜索树问题的带深度限制扩展。关键点在于状态增加高度维度，转移时左右子树的高度上限减 1。需要注意空子树的处理（代价为 0，概率已计入父树的 w 中），以及高度为 0 时非空子树的不可行性。算法复杂度为 O(n³D)，可用于中等规模的 n 和 D。