最优二叉搜索树问题（带成功和失败频率版本） 题目描述：给定一组有序键（如二叉搜索树中的键）以及每个键被搜索成功的频率，同时还给定搜索失败（即搜索值不在键中）的频率分布。具体来说，有n个键K1, K2, ..., Kn（按升序排列），每个键Ki有一个成功搜索频率pi。同时，有n+1个“虚拟键”代表搜索失败的情况，其频率为q0, q1, ..., qn，其中q0表示搜索值小于K1的失败频率，qi表示搜索值在Ki和K(i+1)之间的失败频率，qn表示搜索值大于Kn的失败频率。目标是构建一棵二叉搜索树，使得所有搜索（包括成功和失败）的期望比较次数最小。 解题过程： 问题分析： 二叉搜索树的搜索成本取决于节点的深度。成功搜索键Ki的成本与其深度depth(Ki)有关，贡献为pi * (depth(Ki) + 1)。 失败搜索（虚拟键）的成本也类似，对于频率qi，其对应的失败区间在树中有一个“叶子节点”位置，成本为qi * (depth(叶子) + 1)，但注意在二叉搜索树中，失败搜索最终会到达一个空子树，通常将失败频率qi关联到叶子节点，其深度即为叶子节点的深度。 总期望成本E = Σ(pi * (depth(Ki) + 1)) + Σ(qi * (depth(虚拟键i) + 1))，其中i从1到n（成功）和i从0到n（失败）。 目标是构造BST使得E最小。 动态规划状态定义： 定义子问题：设e[ i][ j ]表示由键Ki, K(i+1), ..., Kj构成的二叉搜索树的最小期望搜索成本（包括成功和失败频率）。 同时，为了计算方便，定义w[ i][ j]为子树中所有键的成功频率和失败频率的总和，即w[ i][ j] = Σpm (从i到j) + Σqm (从i-1到j)。注意，这里包括的失败频率是从q(i-1)到qj，因为对于键区间[ i, j ]，其对应的失败区间有j-i+2个（包括两端的失败情况）。 初始时，当j = i-1时，表示没有实际键，只有失败频率q(i-1)，此时树为一棵空树，期望成本即为q(i-1)。 状态转移方程： 考虑以键Kr（i ≤ r ≤ j）作为根节点，则左子树包含键Ki, ..., K(r-1)，右子树包含键K(r+1), ..., Kj。 左子树的期望成本为e[ i][ r-1]，右子树的期望成本为e[ r+1][ j ]。 当以Kr为根时，左子树和右子树中每个节点的深度都增加1，因此总成本会增加一个量，等于左子树和右子树中所有频率的总和（因为每个频率的深度增加1，成本增加该频率值）。 而左子树和右子树的所有频率总和正好是w[ i][ j] - pr（因为w[ i][ j ]是整棵子树的总频率，减去根的成功频率pr，就是左右子树的总频率）。 因此，以Kr为根的最小成本为：e[ i][ r-1] + e[ r+1][ j] + w[ i][ j ] - pr。 但注意，根节点Kr本身的成本是pr * 1（因为深度为0，比较次数为1），而上述左右子树的成本已经包含了根节点下所有节点的深度增加带来的成本，加上根节点pr的成本，总成本就是e[ i][ r-1] + e[ r+1][ j] + w[ i][ j ]。 验证：e[ i][ r-1]和e[ r+1][ j]是左右子树作为独立树时的成本，当它们作为子树时，每个节点的深度+1，所以成本增加量就是左右子树的总频率（即w[ i][ j] - pr），然后加上根节点的成本pr，总增加为w[ i][ j]。因此转移方程为：e[ i][ j] = min_ {i ≤ r ≤ j} { e[ i][ r-1] + e[ r+1][ j] + w[ i][ j ] }。 特殊情况：当r = i时，左子树无键，只有失败频率q(i-1)，此时e[ i][ i-1] = q(i-1)（根据定义）。同理，当r = j时，右子树e[ j+1][ j ] = qj。 计算顺序： 需要计算e[ i][ j ]对于所有1 ≤ i ≤ j ≤ n。 按区间长度L从0到n-1递增计算（L = j - i）。 对于每个L，遍历所有起始点i，计算j = i + L。 同时，预计算w[ i][ j]：可以初始化w[ i][ i-1] = q(i-1)，然后w[ i][ j] = w[ i][ j-1 ] + pj + qj。 算法步骤： 初始化数组e和w，大小为(n+1) x (n+1)（索引从1到n，但需要处理边界到0和n+1）。 对于i从1到n+1，设置e[ i][ i-1 ] = q(i-1)（表示空树的成本）。 对于L从0到n-1（区间长度）： 对于i从1到n-L： j = i + L 设置e[ i][ j ] = 无穷大 计算w[ i][ j]：如果L=0，则w[ i][ j] = w[ i][ j-1] + pj + qj，但注意w[ i][ i-1]已初始化为q(i-1)，所以w[ i][ i] = w[ i][ i-1 ] + pi + qi = q(i-1) + pi + qi。 对于r从i到j： 计算成本c = e[ i][ r-1] + e[ r+1][ j] + w[ i][ j ] 如果c < e[ i][ j]，则更新e[ i][ j ] = c 最终结果在e[ 1][ n ]中。 时间复杂度：O(n^3)，因为有三层循环（区间长度、起始点、根位置）。空间复杂度O(n^2)。 通过这个动态规划过程，我们可以找到构建最优二叉搜索树的最小期望搜索成本。