区间动态规划例题：最小分割成本构造平衡二叉搜索树问题

题目描述

给定一个排序后的整数数组 nums，以及一个函数 cost(i, j)，它表示以 nums[i..j] 这个子数组中的元素作为节点，构造一棵平衡二叉搜索树（AVL树或任何平衡树）的 最小额外成本。这里的“额外成本”定义如下：当选择 nums[k]（i ≤ k ≤ j）作为当前子树的根节点时，其左子树由 nums[i..k-1] 构成，右子树由 nums[k+1..j] 构成，那么构造当前子树的成本是：

cost(i, j) = min_{k} [ cost(i, k-1) + cost(k+1, j) + weight(i, j) ]

其中 weight(i, j) 是一个给定的函数，通常与子数组 nums[i..j] 的 总和 或 某个统计量 相关，表示以该子数组构建子树时的 基础开销（例如，子树中所有节点深度之和的增量、访问频率加权和等）。

目标：计算 cost(0, n-1)，即用整个数组构建平衡二叉搜索树的最小总成本。

解题思路

这个问题是 最优二叉搜索树（Optimal Binary Search Tree, OBST） 的一个变体。在经典OBST问题中，我们通常给定每个键的访问频率，目标是最小化搜索代价的期望值（即每个节点的深度乘频率之和）。而这里，我们把“频率”推广为任意的区间权重 weight(i, j)，它可能依赖于区间内元素的和或其他属性。

步骤 1：问题抽象与状态定义

• 输入数组 nums 长度为 n，并且已排序（这样 BST 的中序遍历就是 nums 本身）。
• 定义 dp[i][j] 表示用子数组 nums[i..j] 构造一棵平衡二叉搜索树的最小成本。
• 我们最终目标是计算 dp[0][n-1]。

步骤 2：状态转移方程

假设我们选择 nums[k] 作为根节点（i ≤ k ≤ j），那么：

• 左子树对应的子数组为 nums[i..k-1]，最小成本为 dp[i][k-1]（当 k > i 时，否则左子树为空，成本为 0）。
• 右子树对应的子数组为 nums[k+1..j]，最小成本为 dp[k+1][j]（当 k < j 时，否则右子树为空，成本为 0）。
• 将左右子树连接到根节点，会产生一个额外的 基础开销 weight(i, j)。这个开销可能与区间内所有元素的和有关（例如，如果 weight(i, j) = sum(nums[i..j])，那么它相当于所有节点深度加 1 带来的成本增量）。

因此，状态转移方程为：

dp[i][j] = min_{k = i..j} [ dp[i][k-1] + dp[k+1][j] + weight(i, j) ]

其中：

• 如果 k == i，则 dp[i][k-1] = 0（左子树为空）。
• 如果 k == j，则 dp[k+1][j] = 0（右子树为空）。
• 我们还需要预先计算出所有区间的 weight(i, j)，通常用前缀和快速得到区间和。

步骤 3：边界条件与初始化

• 当 i > j 时，区间为空，对应空子树，成本为 0。但我们的循环通常从小区间向大区间递推，所以只需初始化长度为 1 的区间：

  dp[i][i] = weight(i, i)   // 只有根节点，成本就是该节点自身的权重
  

• weight(i, j) 需要根据题目具体定义计算。常见定义为区间和：

  weight(i, j) = sum(nums[i..j])
  

  可以用前缀和数组 prefix 快速计算：sum(i, j) = prefix[j+1] - prefix[i]。

步骤 4：计算顺序

典型的区间 DP 计算顺序：按区间长度 len 从小到大计算。

1. 外层循环：len = 1 到 n。
2. 内层循环：枚举区间起点 i，计算终点 j = i + len - 1。
3. 对于每个区间 [i, j]，枚举根节点位置 k，根据转移方程计算 dp[i][j]。

时间复杂度：状态数 O(n²)，每个状态枚举根节点 O(n)，总复杂度 O(n³)。
空间复杂度：O(n²)。

举例说明

假设 nums = [1, 2, 3, 4]，weight(i, j) = sum(nums[i..j])。

前缀和：prefix = [0, 1, 3, 6, 10]。

计算过程：

1. 初始化长度为 1 的区间：

   • dp[0][0] = sum(0,0) = 1
   • dp[1][1] = 2
   • dp[2][2] = 3
   • dp[3][3] = 4

2. 长度 len = 2：

   • [0,1]：枚举 k=0,1
     • k=0：左空(0) + 右dp[1][1]=2 + sum(0,1)=3 → 5
     • k=1：左dp[0][0]=1 + 右空(0) + sum(0,1)=3 → 4
     • 取最小值 4 → dp[0][1] = 4
   • [1,2]：类似计算，得 dp[1][2] = min(2+0+5, 1+3+5) = min(7,9) = 7
   • [2,3]：dp[2][3] = min(3+0+7, 2+4+7) = min(10,13) = 10

3. 长度 len = 3：

   • [0,2]：枚举 k=0,1,2
     • k=0: 0 + dp[1][2]=7 + sum(0,2)=6 → 13
     • k=1: dp[0][0]=1 + dp[2][2]=3 + 6 → 10
     • k=2: dp[0][1]=4 + 0 + 6 → 10
     • 取最小值 10 → dp[0][2] = 10
   • [1,3]：类似计算得 dp[1][3] = min(2+10+9, 7+4+9, 1+4+9) = min(21,20,14) = 14

4. 长度 len = 4：

   • [0,3]：枚举 k=0,1,2,3
     • k=0: 0 + dp[1][3]=14 + sum(0,3)=10 → 24
     • k=1: dp[0][0]=1 + dp[2][3]=10 + 10 → 21
     • k=2: dp[0][1]=4 + dp[3][3]=4 + 10 → 18
     • k=3: dp[0][2]=10 + 0 + 10 → 20
     • 取最小值 18 → dp[0][3] = 18

最终结果：dp[0][3] = 18，即构建整个树的最小成本为 18。

优化考虑

1. 四边形不等式优化：如果 weight(i, j) 满足四边形不等式（通常区间和满足），则可以用 Knuth 优化将枚举 k 的复杂度从 O(n) 降为 O(1)，从而使总复杂度降至 O(n²)。
   优化核心：记录使 dp[i][j] 最小的 k 的位置 opt[i][j]，则有：

   opt[i][j-1] ≤ opt[i][j] ≤ opt[i+1][j]
   

   这样在枚举 k 时只需在 opt[i][j-1] 到 opt[i+1][j] 范围内搜索。

2. 不同的 weight 函数：

   • 如果 weight(i, j) = 1，则问题退化为 Catalan 数计数（不同 BST 的数量）。
   • 如果 weight(i, j) = sum(i, j)，则相当于最小化 所有节点深度之和（因为每层递归都会加上当前子树的所有节点值，相当于每个节点值被累加的次数等于其深度）。

核心总结

• 状态定义：dp[i][j] 表示用有序子数组 nums[i..j] 构造平衡 BST 的最小成本。
• 转移方程：dp[i][j] = min_{k} dp[i][k-1] + dp[k+1][j] + weight(i, j)。
• 计算顺序：区间长度从小到大。
• 常见 weight：区间和，此时问题等价于 带权 OBST，其中每个节点的“频率”就是它的值。
• 优化：四边形不等式可加速。

这个模型可以灵活适应不同的 weight 定义，用于求解一类“基于有序序列构建二叉树，最小化某种累计成本”的问题。