线性动态规划：石子合并（区间DP）

题目描述

你有一排堆成直线的n堆石子，其中第i堆石子的数量为stones[i]。你的任务是将这排石子合并成一堆。每次只能合并相邻的两堆石子，合并的代价是这两堆石子的数量之和。合并后，新堆的石子数等于原两堆石子数之和，并与相邻堆继续保持相邻关系。你需要找出将全部石子合并成一堆的最小总代价。

示例：

• 输入：stones = [3, 4, 2, 1]
• 输出：20
• 解释：
  1. 合并 [2, 1]，代价 = 3，新数组 [3, 4, 3]，总代价 = 3。
  2. 合并 [3, 4]，代价 = 7，新数组 [7, 3]，总代价 = 3 + 7 = 10。
  3. 合并 [7, 3]，代价 = 10，总代价 = 10 + 10 = 20。
     另一种合并顺序可能代价更大，20是最小总代价。

解题过程（区间动态规划）

这个问题属于区间DP，因为每次操作影响的是一个连续区间内的石子堆，且最终状态由整个区间合并而来。我们的目标是找到最优的合并顺序，使得总代价最小。

步骤1：理解问题本质

• 合并n堆石子的过程可以看作是一棵二叉树（合并树），叶子是初始石子堆，内部节点是合并结果，节点值等于子树叶子值之和。
• 总代价 = 所有内部节点值之和（因为每个内部节点的值就是一次合并的代价）。
• 在二叉树中，每个叶子（石子堆）在最终总代价中的贡献次数等于它到根路径上的边数（即合并次数）。
• 由于每次只能合并相邻堆，这意味着合并树中任意子树对应的石子堆必须是原始数组的一个连续子数组。

因此，问题转化为：将一个连续数组划分成子树，使得内部节点值总和最小。

步骤2：定义DP状态

设 dp[i][j] 表示将第 i 堆到第 j 堆石子（闭区间）合并成一堆的最小总代价。

• i 和 j 是数组索引，满足 0 ≤ i ≤ j < n。
• 最终答案是 dp[0][n-1]。

关键思考：最后一次合并前，区间 [i, j] 一定是由两个连续子区间合并而来。假设最后一次合并发生在位置 k，即先合并 [i, k] 成为一堆，再合并 [k+1, j] 成为一堆，然后将这两堆合并。那么：

dp[i][j] = min{ dp[i][k] + dp[k+1][j] + sum(i, j) }，其中 i ≤ k < j

这里 sum(i, j) 是区间 [i, j] 的石子总数，因为最后一步合并的代价就是这两个大堆的石子数之和，而这两个大堆的石子数之和正是整个区间石子总数。

步骤3：前缀和优化区间求和

为了快速计算任意区间 [i, j] 的和，我们提前计算前缀和数组 prefix：

• prefix[0] = 0
• prefix[k] = stones[0] + stones[1] + ... + stones[k-1]（前k个元素的和）
  则 sum(i, j) = prefix[j+1] - prefix[i]。

步骤4：确定计算顺序

区间DP常见的计算顺序是：按区间长度从小到大计算。

• 长度 len = 1 时，区间只有一堆石子，无需合并，代价为0（dp[i][i] = 0）。
• 长度 len = 2 时，区间有两堆石子，只能直接合并，代价为 stones[i] + stones[j]。
• 对于更长的区间，我们枚举分割点 k，将区间分成 [i, k] 和 [k+1, j]，利用已计算好的更短区间的结果。

步骤5：状态转移方程

dp[i][j] = 0，当 i == j（区间长度为1）
dp[i][j] = min{ dp[i][k] + dp[k+1][j] + sum(i, j) }，对 i ≤ k < j

其中 sum(i, j) = prefix[j+1] - prefix[i]。

步骤6：算法实现

1. 计算前缀和数组 prefix。
2. 初始化 dp 数组（二维，大小为 n × n），所有元素设为0（实际上长度1的区间代价为0，长度≥2的初始化为一个较大值）。
3. 按区间长度 len 从2到 n 遍历：
   • 对于每个起点 i（0 ≤ i ≤ n - len），计算终点 j = i + len - 1。
   • 初始化 dp[i][j] 为一个很大的数（例如 INT_MAX）。
   • 枚举分割点 k 从 i 到 j-1：

     cost = dp[i][k] + dp[k+1][j] + (prefix[j+1] - prefix[i])
     dp[i][j] = min(dp[i][j], cost)
     

4. 返回 dp[0][n-1]。

步骤7：复杂度分析

• 时间复杂度：O(n³)，因为三层循环（区间长度、起点、分割点）。
• 空间复杂度：O(n²)，存储 dp 表。

步骤8：示例推导

以 stones = [3, 4, 2, 1] 为例：

• 前缀和 prefix = [0, 3, 7, 9, 10]（prefix[i] 表示前i个元素的和）。
• 初始化 dp[i][i] = 0。

长度为2：

• [0,1]：dp[0][1] = dp[0][0] + dp[1][1] + sum(0,1) = 0 + 0 + 7 = 7
• [1,2]：dp[1][2] = 0 + 0 + 6 = 6
• [2,3]：dp[2][3] = 0 + 0 + 3 = 3

长度为3：

• [0,2]：枚举 k=0,1
  • k=0：dp[0][0] + dp[1][2] + sum(0,2) = 0 + 6 + 9 = 15
  • k=1：dp[0][1] + dp[2][2] + sum(0,2) = 7 + 0 + 9 = 16
  • 取最小值 dp[0][2] = 15
• [1,3]：枚举 k=1,2
  • k=1：dp[1][1] + dp[2][3] + sum(1,3) = 0 + 3 + 7 = 10
  • k=2：dp[1][2] + dp[3][3] + sum(1,3) = 6 + 0 + 7 = 13
  • dp[1][3] = 10

长度为4（整个数组 [0,3]）：

• sum(0,3) = 10
• 枚举 k=0,1,2：
  • k=0：dp[0][0] + dp[1][3] + 10 = 0 + 10 + 10 = 20
  • k=1：dp[0][1] + dp[2][3] + 10 = 7 + 3 + 10 = 20
  • k=2：dp[0][2] + dp[3][3] + 10 = 15 + 0 + 10 = 25
  • 取最小值 dp[0][3] = 20 ✅

最终得到最小总代价为20。

总结

石子合并问题是区间DP的经典入门题，其核心在于：

1. 识别区间性质：每次合并影响连续区间。
2. 定义状态：dp[i][j] 表示合并区间 [i, j] 的最小代价。
3. 状态转移：枚举最后一次合并的分割点，将大区间拆成两个已合并好的小区间。
4. 前缀和优化：快速得到任意区间和。
5. 计算顺序：按区间长度从小到大递推。

掌握这个模型后，你可以解决许多类似问题，如多边形三角剖分求最优值、字符串折叠等，它们都具有“将大区间分解为两个子区间并组合结果”的结构。