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

题目描述
给定一个有序的键值序列 keys（如 [k1, k2, ..., kn]）和对应的搜索频率 freq（如 [f1, f2, ..., fn]），要求构造一棵二叉搜索树（BST），使得所有键的总搜索成本最小。搜索成本定义为键的深度（从根节点开始的层数）乘以频率的总和。形式化地，若键 ki 的深度为 d(ki)，则总成本为：
总成本 = Σ (freq[i] * (d(keys[i]) + 1))
其中深度从根节点的0开始计算，d(ki) + 1 表示访问该键所需的比较次数。

解题思路

1. 问题分析：

   • 二叉搜索树的中序遍历必须与 keys 的顺序一致。
   • 若以某个键 kr 为根，则左子树包含键 [ki, ..., kr-1]，右子树包含 [kr+1, ..., kj]。
   • 总成本包括根节点的成本（频率 × 1）加上左右子树的成本（子树中每个键的深度增加1，相当于其频率被多计算一次）。

2. 动态规划定义：
   设 dp[i][j] 表示由键 keys[i..j] 构成的二叉搜索树的最小总成本（i 和 j 为键的索引）。
   状态转移方程：

   dp[i][j] = min_{r=i..j} {
       dp[i][r-1] + dp[r+1][j] + sum(freq[i..j])
   }
   

   其中 sum(freq[i..j]) 是区间 [i, j] 内所有频率之和，表示以 kr 为根时，子树中所有键的深度增加1导致的额外成本。

3. 初始化与计算顺序：

   • 空子树成本为0：当 i > j 时，dp[i][j] = 0。
   • 按区间长度从小到大计算：先计算长度为1的区间（单节点），再逐步扩大区间。

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

1. 计算单节点区间（长度=1）：

   • dp[0][0] = 3（只有键10）
   • dp[1][1] = 2（只有键20）
   • dp[2][2] = 5（只有键30）

2. 计算长度为2的区间：

   • 区间 [0,1]（键10和20）：
     • 根为10：成本 = dp[0][-1]（空） + dp[1][1] + sum(3,2) = 0 + 2 + 5 = 7
     • 根为20：成本 = dp[0][0] + dp[2][1]（空） + 5 = 3 + 0 + 5 = 8
     • dp[0][1] = min(7, 8) = 7
   • 区间 [1,2]（键20和30）：
     • 根为20：成本 = 0 + 5 + (2+5) = 7
     • 根为30：成本 = 2 + 0 + 7 = 9
     • dp[1][2] = min(7, 9) = 7

3. 计算长度为3的区间（[0,2]）：

   • 根为10：成本 = 0 + dp[1][2] + sum(3,2,5) = 0 + 7 + 10 = 17
   • 根为20：成本 = dp[0][0] + dp[2][2] + 10 = 3 + 5 + 10 = 18
   • 根为30：成本 = dp[0][1] + 0 + 10 = 7 + 0 + 10 = 17
   • dp[0][2] = min(17, 18, 17) = 17

最终最小总成本为 dp[0][2] = 17。

总结
通过区间动态规划，枚举每个区间内所有可能的根节点，利用子问题的最优解组合得到当前区间的最优解，确保时间复杂度为 O(n³)（n为键的数量）。