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

题目描述
假设有一组有序的关键字序列（如二叉搜索树的节点值）K = [k1, k2, ..., kn]，以及每个关键字被搜索成功的概率P = [p1, p2, ..., pn]。同时，对于关键字之间的区间（即搜索失败的情况），也有对应的失败概率Q = [q0, q1, ..., qn]，其中q0表示搜索值小于k1的概率，q_i（i从1到n-1）表示搜索值在ki和k_{i+1}之间的概率，qn表示搜索值大于kn的概率。目标是构建一棵二叉搜索树，使得所有搜索操作（包括成功和失败）的期望比较次数最小。

解题过程

1. 问题分析

   • 二叉搜索树的搜索成本取决于树的结构。每次搜索从根节点开始，比较目标值与当前节点值，根据比较结果进入左子树或右子树，直到找到目标（成功）或到达空节点（失败）。
   • 期望比较次数 = Σ(每个节点的深度 × 成功概率) + Σ(每个空节点的深度 × 失败概率)。深度指从根节点到该节点的路径长度（根节点深度为1）。
   • 目标：通过调整树的结构，最小化期望比较次数。

2. 定义状态

   • 设dp[i][j]表示由关键字ki到kj构成的子树（包括对应的失败区间）的最小期望搜索成本。
   • 初始时，考虑空子树：dp[i][i-1]表示仅包含失败概率q_{i-1}的子树（即关键字区间为空），其成本即为q_{i-1}（因为直接失败，比较次数为1）。

3. 状态转移方程

   • 对于区间[i, j]，依次尝试每个关键字kr（i ≤ r ≤ j）作为根节点：
     • 左子树包含关键字ki到k_{r-1}，对应的最小成本为dp[i][r-1]。
     • 右子树包含关键字k_{r+1}到kj，对应的最小成本为dp[r+1][j]。
     • 当以kr为根时，所有成功和失败概率的成本需重新计算：
       • 根节点kr的深度为1，其成功概率pr贡献的成本为1 * pr。
       • 左子树和右子树中所有节点的深度增加1，因此成本需加上整棵子树的概率和（因为深度增加1意味着比较次数多一次）。
     • 整棵子树的总概率和 = 成功概率之和（p_i到p_j） + 失败概率之和（q_{i-1}到q_j）。
   • 转移方程：

     dp[i][j] = min_{r=i to j} {
         dp[i][r-1] + dp[r+1][j] + (p_i + ... + p_j) + (q_{i-1} + ... + q_j)
     }
     

     其中，(p_i + ... + p_j) + (q_{i-1} + ... + q_j)是区间[i, j]的总概率和，记为w(i, j)。
   • 注意边界：当i > j时，dp[i][j] = 0（因为无关键字，但失败概率已通过w(i, j)包含）。

4. 计算顺序

   • 按区间长度从小到大计算：先计算长度为0的区间（即dp[i][i-1] = q_{i-1}），然后长度从1到n逐步增加。
   • 对于每个区间[i, j]，遍历所有可能的根节点r，计算最小成本。

5. 示例演示
   假设n=3，关键字概率P=[0.1, 0.2, 0.3]，失败概率Q=[0.05, 0.1, 0.05, 0.1]。

   • 计算w(i, j)：例如w(1,3) = p1+p2+p3 + q0+q1+q2+q3 = 0.1+0.2+0.3+0.05+0.1+0.05+0.1 = 0.9。
   • 计算dp[1][1]：以k1为根，成本 = dp[1][0] + dp[2][1] + w(1,1) = q0 + 0 + (p1+q0+q1) = 0.05 + 0 + (0.1+0.05+0.1) = 0.3。
   • 类似地计算所有区间，最终dp[1][3]即为最小期望成本。

6. 复杂度分析

   • 时间复杂度：O(n³)，需要三重循环（区间长度、起点、根节点位置）。
   • 空间复杂度：O(n²)，用于存储dp表。

通过以上步骤，可系统地求解最优二叉搜索树问题，确保在包含成功和失败概率的情况下最小化搜索成本。