最优二叉搜索树问题

问题描述
给定一个有序序列的键值集合 keys（如 [k1, k2, ..., kn]，满足 k1 < k2 < ... < kn）以及每个键值的搜索频率 freq（如 [f1, f2, ..., fn]）。要求构建一棵二叉搜索树（BST），使得所有键值的总搜索成本最小。搜索成本定义为键值的深度（从根节点开始为1）乘以其频率的总和，即：
总成本 = Σ(键值i的深度 × 频率fi)。
例如，若键值 ki 在深度 d 被找到，则其成本为 d * fi。目标是找到一棵BST，使得总成本最小。

解题思路

1. 问题分析：

   • 二叉搜索树的中序遍历必须与 keys 的顺序一致。
   • 若以键值 kr 为根，则左子树包含 keys[i..r-1]，右子树包含 keys[r+1..j]。
   • 子树深度增加会导致整体成本上升，因此需平衡频率高的键值放在浅层。

2. 区间DP定义：
   设 dp[i][j] 表示由键值 keys[i..j] 构建的最小搜索成本（i 和 j 为区间索引）。
   最终目标是求解 dp[0][n-1]。

3. 状态转移方程：

   • 枚举区间 [i, j] 中的每个键值 kr（i ≤ r ≤ j）作为根节点。
   • 左子树成本为 dp[i][r-1]，右子树成本为 dp[r+1][j]。
   • 当以 kr 为根时，子树中所有键值的深度均+1，因此需加上整个区间 [i, j] 的频率和（即 sum(freq[i..j])）。
   • 转移方程：

     dp[i][j] = min{ 
       dp[i][r-1] + dp[r+1][j] + sum(freq[i..j]) 
     }，其中 r 从 i 到 j
     

     注意：当 i > j 时，子树为空，成本为0。

4. 预处理频率和：
   使用前缀和数组 prefixSum，使得 sum(freq[i..j]) = prefixSum[j+1] - prefixSum[i]，以便快速计算。

5. 计算顺序：
   按区间长度从小到大计算：先计算长度为1的区间，再逐步扩展到长度为n的区间。

示例与步骤
假设 keys = [10, 20, 30]，频率 freq = [3, 2, 5]。

• 前缀和：prefixSum = [0, 3, 5, 10]（索引0为辅助值）。
• 初始化：单个节点的成本即其频率（深度为1）。
  • dp[0][0] = 3，dp[1][1] = 2，dp[2][2] = 5。
• 区间长度=2：
  • [0,1]：根为10时：左空(0) + 右(2) + 频率和(3+2=5) = 7；根为20时：左(3) + 右空(0) + 5 = 8。取最小值7。
  • [1,2]：根为20时：左空(0) + 右(5) + 频率和(2+5=7) = 12；根为30时：左(2) + 右空(0) + 7 = 9。取最小值9。
• 区间长度=3：
  • [0,2]：
    • 根为10：左空(0) + 右dp[1][2]=9 + 频率和(3+2+5=10) = 19。
    • 根为20：左dp[0][0]=3 + 右dp[2][2]=5 + 10 = 18。
    • 根为30：左dp[0][1]=7 + 右空(0) + 10 = 17。
    • 最小值17为最终结果。

总结
通过区间DP枚举所有可能的子树结构，确保高频键值靠近根节点，从而最小化总搜索成本。时间复杂度为O(n³)，空间复杂度为O(n²)。