区间动态规划例题：最优二叉搜索树问题（带成功和失败频率版本）

字数 2730 2025-11-28 11:21:17

区间动态规划例题：最优二叉搜索树问题（带成功和失败频率版本）

题目描述

给定一组有序的关键字序列（例如，关键字按升序排列：k1, k2, ..., kn），以及每个关键字被成功搜索到的频率（p1, p2, ..., pn）。同时，我们还给定一系列“虚拟关键字”，代表搜索值可能落在关键字区间之外的情况（例如，小于k1，介于k1和k2之间，...，大于kn），每个虚拟关键字被搜索（即搜索失败）的频率（q0, q1, ..., qn）。
我们的目标是构建一棵二叉搜索树（BST），使得所有搜索操作（包括成功和失败）的期望比较次数最小。

期望比较次数可以理解为：搜索一个关键字的成本（即从根节点到该关键字节点的路径长度+1）乘以该关键字被搜索的频率，对所有成功和失败的情况求和。

形式化地，总期望成本 E 为：
E = Σ (成功搜索关键字 ki 的成本 * pi) + Σ (失败搜索虚拟关键字 di 的成本 * qi)
其中，虚拟关键字 di 对应区间 (ki, ki+1)（以及两端的区间）。

解题过程

问题分析与子问题定义
这是一个经典的区间动态规划问题。关键在于，为了构建一棵期望搜索成本最小的BST，我们需要为每个连续的关键字区间选择根节点。一旦根节点选定，左右子树就变成了独立的子问题（即构建左区间和右区间的最小期望成本BST）。

我们定义子问题：
令 dp[i][j] 表示由关键字 ki, ki+1, ..., kj 构成的二叉搜索树的最小期望搜索成本（其中 1 <= i <= j <= n）。注意，这个子树包含了虚拟关键字：在关键字序列两端的虚拟关键字（q(i-1) 和 qj）以及关键字之间的虚拟关键字。

为了处理边界情况（空子树），我们扩展定义：
令 dp[i][i-1] 表示一个不包含任何实际关键字，只包含一个虚拟关键字（对应区间 (k(i-1), ki)）的“空树”的期望成本。实际上，这个空树就是一个叶子节点的失败情况。其成本就是虚拟关键字本身的频率 q(i-1)（因为搜索到达这个空树只需要一次比较）。
状态转移方程
考虑如何计算 dp[i][j]。
- 选择根节点：我们尝试将区间 [i, j] 内的每一个关键字 kr (i <= r <= j) 作为根节点。
- 左右子树：如果 kr 是根，那么左子树包含关键字 ki, ..., k(r-1)，其最小成本是 dp[i][r-1]。右子树包含关键字 k(r+1), ..., kj，其最小成本是 dp[r+1][j]。
- 成本增加：当我们将左右子树连接到根节点 kr 时，子树中每个节点的深度都增加了1。这意味着，对于左子树和右子树中包含的所有关键字（包括成功和失败的虚拟关键字），它们的搜索成本都增加了1次比较。
  那么，以 kr 为根时，整棵子树 [i, j] 的总成本为：
  cost = (dp[i][r-1] + 左子树中所有频率之和) + (dp[r+1][j] + 右子树中所有频率之和) + pr
  解释：
  - dp[i][r-1] 是左子树原有的成本。因为左子树所有节点深度+1，所以总成本额外增加了左子树中所有关键字（成功和失败）的频率和。
  - 同理，右子树成本增加了右子树中所有频率和。
  - pr 是根节点 kr 本身的搜索成本（深度为0，比较次数为1，所以成本是 1 * pr）。
- 频率和的计算：左子树 [i, r-1] 包含了所有成功关键字 ki, ..., k(r-1) 和所有相关的虚拟关键字（频率从 q(i-1) 到 q(r-1)）。右子树 [r+1, j] 类似。
  实际上，整个区间 [i, j] 的频率和（包括成功关键字频率 p 和虚拟关键字频率 q）是一个定值，记为 w(i, j) = Σ_{t=i}^{j} pt + Σ_{t=i-1}^{j} qt。
  那么，左子树的频率和就是 w(i, r-1)，右子树的频率和是 w(r+1, j)。
  注意：w(i, j) = w(i, r-1) + pr + w(r+1, j)。
- 简化成本表达式：将上述成本表达式展开：
  cost = dp[i][r-1] + w(i, r-1) + dp[r+1][j] + w(r+1, j) + pr
  因为 w(i, r-1) + pr + w(r+1, j) = w(i, j)，所以：
  cost = dp[i][r-1] + dp[r+1][j] + w(i, j)
- 状态转移方程：我们需要遍历所有可能的根节点 r，选择成本最小的那个：
  dp[i][j] = min_{r from i to j} { dp[i][r-1] + dp[r+1][j] } + w(i, j)
  其中，w(i, j) = Σ_{t=i}^{j} pt + Σ_{t=i-1}^{j} qt
- 边界条件：对于空子树，dp[i][i-1] = q(i-1)。
计算顺序与初始化
- 我们需要按照区间长度从小到大的顺序计算。
- 区间长度 L 从 1 到 n（L = j - i + 1）。
- 对于每个区间长度 L，遍历所有可能的起始点 i（从而 j = i + L -1）。
- 对于每个固定的区间 [i, j]，遍历所有可能的根节点 r (i <= r <= j)，计算 dp[i][j]。
最终结果
最终要求的是包含所有关键字 [1, n] 的BST的最小期望成本，即 dp[1][n]。
示例说明（简化）
假设有 n=1 个关键字 k1。
成功频率 p1 = 0.3
虚拟关键字频率：q0=0.1, q1=0.2 (q0对应<k1, q1对应>k1)
w(1,1) = p1 + q0 + q1 = 0.3 + 0.1 + 0.2 = 0.6
可能的根节点只有 r=1。
dp[1][1] = min{ dp[1][0] + dp[2][1] } + w(1,1)
根据边界条件：dp[1][0] = q0 = 0.1 (空左子树)
dp[2][1] = q1 = 0.2 (空右子树，因为2>1，代表右子树为空)
dp[1][1] = (0.1 + 0.2) + 0.6 = 0.9
这棵树的期望成本：根节点k1成本=1p1=0.3；左虚拟叶子成本=2q0=0.2（深度1，比较2次）；右虚拟叶子成本=2*q1=0.4（深度1，比较2次）。总成本=0.3+0.2+0.4=0.9，符合。

通过这种自底向上的动态规划方法，我们可以高效地找到构建最优二叉搜索树的方法。

区间动态规划例题：最优二叉搜索树问题（带成功和失败频率版本）题目描述给定一组有序的关键字序列（例如，关键字按升序排列：k1, k2, ..., kn），以及每个关键字被成功搜索到的频率（p1, p2, ..., pn）。同时，我们还给定一系列“虚拟关键字”，代表搜索值可能落在关键字区间之外的情况（例如，小于k1，介于k1和k2之间，...，大于kn），每个虚拟关键字被搜索（即搜索失败）的频率（q0, q1, ..., qn）。我们的目标是构建一棵二叉搜索树（BST），使得所有搜索操作（包括成功和失败）的期望比较次数最小。期望比较次数可以理解为：搜索一个关键字的成本（即从根节点到该关键字节点的路径长度+1）乘以该关键字被搜索的频率，对所有成功和失败的情况求和。形式化地，总期望成本 E 为： E = Σ (成功搜索关键字 ki 的成本 * pi) + Σ (失败搜索虚拟关键字 di 的成本 * qi) 其中，虚拟关键字 di 对应区间 (ki, ki+1)（以及两端的区间）。解题过程问题分析与子问题定义这是一个经典的区间动态规划问题。关键在于，为了构建一棵期望搜索成本最小的BST，我们需要为每个连续的关键字区间选择根节点。一旦根节点选定，左右子树就变成了独立的子问题（即构建左区间和右区间的最小期望成本BST）。我们定义子问题：令 dp[i][j] 表示由关键字 ki, ki+1, ..., kj 构成的二叉搜索树的最小期望搜索成本（其中 1 <= i <= j <= n）。注意，这个子树包含了虚拟关键字：在关键字序列两端的虚拟关键字（q(i-1) 和 qj）以及关键字之间的虚拟关键字。为了处理边界情况（空子树），我们扩展定义：令 dp[i][i-1] 表示一个不包含任何实际关键字，只包含一个虚拟关键字（对应区间 (k(i-1), ki)）的“空树”的期望成本。实际上，这个空树就是一个叶子节点的失败情况。其成本就是虚拟关键字本身的频率 q(i-1) （因为搜索到达这个空树只需要一次比较）。状态转移方程考虑如何计算 dp[i][j] 。选择根节点：我们尝试将区间 [ i, j] 内的每一个关键字 kr (i <= r <= j) 作为根节点。左右子树：如果 kr 是根，那么左子树包含关键字 ki, ..., k(r-1)，其最小成本是 dp[i][r-1] 。右子树包含关键字 k(r+1), ..., kj，其最小成本是 dp[r+1][j] 。成本增加：当我们将左右子树连接到根节点 kr 时，子树中每个节点的深度都增加了1。这意味着，对于左子树和右子树中包含的所有关键字（包括成功和失败的虚拟关键字），它们的搜索成本都增加了1次比较。那么，以 kr 为根时，整棵子树 [ i, j ] 的总成本为： cost = (dp[i][r-1] + 左子树中所有频率之和) + (dp[r+1][j] + 右子树中所有频率之和) + pr 解释： dp[i][r-1] 是左子树原有的成本。因为左子树所有节点深度+1，所以总成本额外增加了左子树中所有关键字（成功和失败）的频率和。同理，右子树成本增加了右子树中所有频率和。 pr 是根节点 kr 本身的搜索成本（深度为0，比较次数为1，所以成本是 1 * pr）。频率和的计算：左子树 [ i, r-1] 包含了所有成功关键字 ki, ..., k(r-1) 和所有相关的虚拟关键字（频率从 q(i-1) 到 q(r-1)）。右子树 [ r+1, j ] 类似。实际上，整个区间 [ i, j] 的频率和（包括成功关键字频率 p 和虚拟关键字频率 q）是一个定值，记为 w(i, j) = Σ_ {t=i}^{j} pt + Σ_ {t=i-1}^{j} qt。那么，左子树的频率和就是 w(i, r-1) ，右子树的频率和是 w(r+1, j) 。注意： w(i, j) = w(i, r-1) + pr + w(r+1, j) 。简化成本表达式：将上述成本表达式展开： cost = dp[i][r-1] + w(i, r-1) + dp[r+1][j] + w(r+1, j) + pr 因为 w(i, r-1) + pr + w(r+1, j) = w(i, j) ，所以： cost = dp[i][r-1] + dp[r+1][j] + w(i, j) 状态转移方程：我们需要遍历所有可能的根节点 r，选择成本最小的那个： dp[i][j] = min_{r from i to j} { dp[i][r-1] + dp[r+1][j] } + w(i, j) 其中， w(i, j) = Σ_{t=i}^{j} pt + Σ_{t=i-1}^{j} qt 边界条件：对于空子树， dp[i][i-1] = q(i-1) 。计算顺序与初始化我们需要按照区间长度从小到大的顺序计算。区间长度 L 从 1 到 n（L = j - i + 1）。对于每个区间长度 L，遍历所有可能的起始点 i（从而 j = i + L -1）。对于每个固定的区间 [ i, j]，遍历所有可能的根节点 r (i <= r <= j)，计算 dp[i][j] 。最终结果最终要求的是包含所有关键字 [ 1, n] 的BST的最小期望成本，即 dp[1][n] 。示例说明（简化）假设有 n=1 个关键字 k1。成功频率 p1 = 0.3 虚拟关键字频率：q0=0.1, q1=0.2 (q0对应 <k1, q1对应>k1) w(1,1) = p1 + q0 + q1 = 0.3 + 0.1 + 0.2 = 0.6 可能的根节点只有 r=1。 dp[1][1] = min{ dp[1][0] + dp[2][1] } + w(1,1) 根据边界条件： dp[1][0] = q0 = 0.1 (空左子树) dp[2][1] = q1 = 0.2 (空右子树，因为2>1，代表右子树为空) dp[1][1] = (0.1 + 0.2) + 0.6 = 0.9 这棵树的期望成本：根节点k1成本=1 p1=0.3；左虚拟叶子成本=2 q0=0.2（深度1，比较2次）；右虚拟叶子成本=2* q1=0.4（深度1，比较2次）。总成本=0.3+0.2+0.4=0.9，符合。通过这种自底向上的动态规划方法，我们可以高效地找到构建最优二叉搜索树的方法。