区间动态规划例题：最优二叉搜索树问题 题目描述 给定一个有序键值集合 keys[ 1..n] 和对应的搜索频率 freq[ 1..n]，其中 keys[ i] 的搜索频率为 freq[ i ]。要求构建一棵二叉搜索树（BST），使得所有键值的总搜索成本最小。搜索成本定义为键值的深度（从根节点开始为1）乘以频率的总和。 形式化定义：对于键值 keys[ i]，其深度为 depth(i)，总成本为 sum(freq[ i] * depth(i)) for i=1 to n。需要构造BST使得该总成本最小。 解题思路 这个问题可以使用区间动态规划解决。定义 dp[ i][ j] 表示由键值 keys[ i..j ] 构建的最优二叉搜索树的最小总成本。我们需要考虑每个可能的根节点，计算左右子树的成本加上当前子树所有节点的频率和（因为根节点的选择会影响所有节点的深度）。 详细步骤 状态定义 定义 dp[ i][ j] 为构建 keys[ i..j ] 的最优BST的最小总成本。 定义 prefixSum 数组，prefixSum[ i] 表示 freq[ 1] 到 freq[ i ] 的和，用于快速计算区间频率和。 状态转移方程 对于区间 [ i, j ]，依次尝试每个键 k (i ≤ k ≤ j) 作为根节点： 左子树 [ i, k-1] 的成本：dp[ i][ k-1 ]（如果 i > k-1 则为0） 右子树 [ k+1, j] 的成本：dp[ k+1][ j ]（如果 k+1 > j 则为0） 当前根节点 k 的深度贡献：由于作为根节点，所有节点深度+1，所以需要加上整个区间 [ i, j ] 的频率和 因此：dp[ i][ j] = min(dp[ i][ k-1] + dp[ k+1][ j] + sum(freq[ i..j])) for k in [ i, j ] 初始化 单个节点：dp[ i][ i] = freq[ i ]（深度为1） 空子树：当 i > j 时，dp[ i][ j ] = 0 计算顺序 按区间长度从小到大计算： 先计算长度为1的区间（单个键） 然后计算长度为2、3...直到n 最终结果 dp[ 1][ n ] 即为由所有键构建的最优BST的最小总成本 举例说明 keys = [ 10, 12, 20]，freq = [ 34, 8, 50 ] 计算 prefixSum：[ 34, 42, 92 ] 长度1： dp[ 1][ 1 ] = 34 dp[ 2][ 2 ] = 8 dp[ 3][ 3 ] = 50 长度2： [ 1,2]：根10：dp[ 2][ 2]+sum=8+42=50；根12：dp[ 1][ 1 ]+sum=34+42=76 → min=50 [ 2,3]：根12：dp[ 3][ 3]+sum=50+58=108；根20：dp[ 2][ 2 ]+sum=8+58=66 → min=66 长度3 [ 1,3 ]： 根10：dp[ 2][ 3 ]+sum=66+92=158 根12：dp[ 1][ 1]+dp[ 3][ 3 ]+sum=34+50+92=176 根20：dp[ 1][ 2 ]+sum=50+92=142 最小成本为142，对应根为20的BST。 算法复杂度 时间复杂度：O(n³)，需要遍历所有区间和根节点 空间复杂度：O(n²)，用于存储dp表 这个算法通过动态规划系统地考虑了所有可能的BST结构，确保了找到全局最优解。