最优二叉搜索树（Optimal Binary Search Tree, OBST）问题
题目描述
我们有一组有序的键（Key） K1 < K2 < ... < Kn，以及对应的搜索频率（概率）p1, p2, ..., pn。此外，我们还有一些不存在的键（即搜索目标不在这个集合中）的区间，可以视为一系列“虚键”（Dummy Keys）d0, d1, ..., dn，其中 d0 表示所有小于 K1 的键，di 表示所有介于 Ki 和 K_{i+1} 之间的键（1 <= i <= n-1），dn 表示所有大于 Kn 的键。每个虚键 di 也有一个被搜索到的频率（概率）q0, q1, ..., qn。
所有频率满足：∑ pi (1 <= i <= n) + ∑ qi (0 <= i <= n) = 1。
目标：构造一棵二叉搜索树（BST），以这些键（实键和虚键）为结点，使得总的期望搜索成本最小。
期望搜索成本定义为：每个结点（实键或虚键）的深度 + 1（即从根到该结点的路径长度，根深度为0）乘以其频率，然后对所有结点求和。
用公式表达：
设结点 x 的频率为 freq(x)，深度为 depth(x)，则总成本 = ∑ freq(x) * (depth(x) + 1)。
我们需要选择一种树的构造方式（即选取根，递归构造左右子树），最小化这个总成本。
解题思路
这是一个经典的区间动态规划问题，因为键是有序的，任何子树必然对应原键序列的一个连续子区间。
-
子问题定义
定义dp[i][j]为：由实键Ki, K_{i+1}, ..., Kj构成的最优二叉搜索树的最小期望搜索成本（这里1 <= i <= j <= n）。
注意：子树中还包含虚键d_{i-1}, d_i, ..., d_j（即这个子树对应的所有虚键）。 -
状态转移方程
对于子区间[i, j]，我们需要选择一个根Kr（i <= r <= j）。
如果选择Kr为根，则：- 左子树包含实键
Ki, ..., K_{r-1}以及虚键d_{i-1}, ..., d_{r-1}。 - 右子树包含实键
K_{r+1}, ..., Kj以及虚键d_r, ..., d_j。
左子树的最小期望成本是
dp[i][r-1]（当r-1 < i时，左子树为空，只有虚键d_{i-1}，其成本为q_{i-1}乘深度增量，但这里我们先不考虑深度增量，稍后统一处理）。更准确地说，
dp[i][j]表示的是：以这个子树为整体，其内部结点的深度是相对于这个子树的根来计算的。但在合并成大树时，子树的每个结点的深度会增加1（因为上面多了一层根）。
所以，当我们计算以Kr为根的子树的总成本时，它包括：- 根
Kr的成本：pr * 1（根深度为0，所以深度+1=1）。 - 左子树的成本：如果左子树非空，其期望成本原本是
dp[i][r-1]，但左子树中每个结点的深度都增加了1（因为现在它们的根Kr是它们的父结点），所以左子树的贡献应该是dp[i][r-1]+ 左子树中所有结点的频率之和（因为每个结点的深度+1，导致成本增加其频率值一次）。 - 右子树同理：
dp[r+1][j]+ 右子树中所有结点的频率之和。
为了计算方便，我们定义
w[i][j]为区间[i, j]中所有实键频率pi..pj加上虚键频率q_{i-1}..q_j的总和。即：
w[i][j] = ∑_{t=i}^{j} pt + ∑_{t=i-1}^{j} qt。那么，以
Kr为根时，总成本为：
cost = pr + (dp[i][r-1] + w[i][r-1]) + (dp[r+1][j] + w[r+1][j])
这里dp[i][r-1]已经包含了左子树内部的成本，w[i][r-1]是左子树所有结点的频率和，加上它是因为左子树每个结点的深度增加了1，成本增加其频率值。
右子树同理。但注意：
dp[i][r-1]在r-1 < i时（左子树为空），我们应将其视为0，且w[i][r-1]应视为q_{i-1}（即只有虚键d_{i-1}的频率）。
为了统一公式，我们约定：当i > j时，dp[i][j] = 0，w[i][j] = q_j（？）
更常见且方便的做法是：预处理前缀和，并在状态转移时直接计算。 - 左子树包含实键
-
预处理频率和
令sum[i][j]表示从i到j的所有实键频率 + 从i-1到j的所有虚键频率之和。
但更简单的方法：
设freq[1..n]为实键频率p1..pn，dummy[0..n]为虚键频率q0..qn。
定义total[i][j] = (∑_{t=i}^{j} pt) + (∑_{t=i-1}^{j} qt)。
我们可以用前缀和快速计算：
令P[i] = p1 + ... + pi，Q[j] = q0 + ... + qj，则
total[i][j] = (P[j] - P[i-1]) + (Q[j] - Q[i-2])（注意边界，i=1时Q[i-2]为0）。 -
简化状态转移
观察公式：
dp[i][j] = min_{r=i..j} { dp[i][r-1] + dp[r+1][j] + (total[i][j]) }
为什么？
因为pr包含在total[i][j]中，而total[i][j]正是整个区间[i, j]所有结点的频率和。
当根为Kr时，总成本 = 左子树成本 + 右子树成本 + 整个区间的频率和（因为根和所有子孙结点的深度都相对增加了，但这里dp[i][r-1]已经是左子树的最小成本（深度从0算），合并后，左子树的每个结点深度+1，所以成本增加左子树的频率和，这个频率和就是total[i][r-1]，同理右子树增加total[r+1][j]。
把这些增加量加上dp[i][r-1] + dp[r+1][j]，再加根的成本pr，会发现总和正好等于：
dp[i][r-1] + dp[r+1][j] + total[i][j]。
因为total[i][j] = pr + total[i][r-1] + total[r+1][j]。 -
最终状态转移方程
所以，递推式为：
dp[i][j] = min_{r=i..j} { dp[i][r-1] + dp[r+1][j] } + total[i][j]
其中dp[i][r-1]在r-1 < i时取0，dp[r+1][j]在r+1 > j时取0。
边界：dp[i][i-1] = 0（表示空区间，只有一个虚键，但虚键成本已经在total中体现，所以这里为0）。 -
计算顺序
区间长度len从 1 到 n 递增。
对每个len，枚举起点i，计算j = i+len-1，然后枚举根r从i到j，更新dp[i][j]。 -
初始化
当区间长度为1（即只有一个实键 Ki）时：
dp[i][i] = min_{r=i..i} { dp[i][r-1] + dp[r+1][i] } + total[i][i] = dp[i][i-1] + dp[i+1][i] + total[i][i]
由于dp[i][i-1] = 0，dp[i+1][i] = 0，所以dp[i][i] = total[i][i]。
而total[i][i] = pi + q_{i-1} + q_i。 -
最终答案
答案为dp[1][n]。
举例说明
假设 n=3，键 K1, K2, K3 频率 p=[0.1, 0.2, 0.3]，虚键 d0,d1,d2,d3 频率 q=[0.05, 0.1, 0.05, 0.1]。
计算 total[i][j]：
total[1][1] = p1 + q0 + q1 = 0.1 + 0.05 + 0.1 = 0.25
total[1][2] = p1+p2 + q0+q1+q2 = 0.1+0.2 + 0.05+0.1+0.05 = 0.5
total[1][3] = 0.1+0.2+0.3 + 0.05+0.1+0.05+0.1 = 0.9
total[2][2] = 0.2 + 0.1+0.05 = 0.35
total[2][3] = 0.2+0.3 + 0.1+0.05+0.1 = 0.75
total[3][3] = 0.3 + 0.05+0.1 = 0.45
然后区间DP：
dp[1][1] = 0.25
dp[2][2] = 0.35
dp[3][3] = 0.45
len=2:
dp[1][2] = min{
r=1: dp[1][0] + dp[2][2] + total[1][2] = 0 + 0.35 + 0.5 = 0.85
r=2: dp[1][1] + dp[3][2] + total[1][2] = 0.25 + 0 + 0.5 = 0.75
} = 0.75
dp[2][3] = min{
r=2: dp[2][1] + dp[3][3] + total[2][3] = 0 + 0.45 + 0.75 = 1.2
r=3: dp[2][2] + dp[4][3] + total[2][3] = 0.35 + 0 + 0.75 = 1.1
} = 1.1
len=3:
dp[1][3] = min{
r=1: dp[1][0] + dp[2][3] + total[1][3] = 0 + 1.1 + 0.9 = 2.0
r=2: dp[1][1] + dp[3][3] + total[1][3] = 0.25 + 0.45 + 0.9 = 1.6
r=3: dp[1][2] + dp[4][3] + total[1][3] = 0.75 + 0 + 0.9 = 1.65
} = 1.6
所以最小期望搜索成本为 1.6。
复杂度
状态数 O(n²)，每个状态枚举根 O(n)，总 O(n³)。可以用四边形不等式优化到 O(n²)，但这里不展开。