石子合并问题（相邻合并，最小成本） 题目描述 有 n 堆石子排成一排，每堆石子有一定的数量。现在要将这些石子合并成一堆。每次只能合并相邻的两堆石子，合并的代价是这两堆石子的数量之和。合并后的新堆石子的数量是这两堆石子的总和，并且新堆会与其它相邻的石子堆形成新的相邻关系。找出一个合并顺序，使得总合并代价最小。 例如，石子数量为 [3, 2, 4, 1] ，一种最优合并顺序是： 合并第2、3堆（代价 2+4=6），石子变为 [3, 6, 1] 合并第1、2堆（代价 3+6=9），石子变为 [9, 1] 合并最后两堆（代价 9+1=10），总代价 = 6 + 9 + 10 = 25。 解题思路 这是一个经典的区间动态规划问题。我们需要定义一个状态 dp[i][j] ，表示将第 i 到第 j 堆石子合并成一堆的最小代价。最终目标是求 dp[1][n] （假设下标从1开始）。 关键步骤 状态定义 dp[i][j] = 合并第 i 到第 j 堆石子的最小代价。 状态转移方程 考虑最后一次合并的位置：假设在合并 [i, j] 时，最后一次合并是将 [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 堆石子的总数量（因为合并最后两堆的代价是它们的总重量）。 初始化 单堆石子不需要合并，代价为0： dp[i][i] = 0 。 为了快速计算区间和，可以预处理前缀和数组 prefix ，使得 sum(i, j) = prefix[j] - prefix[i-1] 。 计算顺序 由于长区间依赖短区间，需要按区间长度 len 从小到大计算： 先枚举区间长度 len = 2 到 n 再枚举区间起点 i = 1 到 n-len+1 ，终点 j = i+len-1 最后枚举分割点 k = i 到 j-1 ，更新 dp[i][j] 。 示例计算（石子 = [ 3, 2, 4, 1]） 预处理前缀和： prefix = [0, 3, 5, 9, 10] （下标从1开始）。 计算过程： len=2 ： dp[1][2] = min(dp[1][1]+dp[2][2]) + sum(1,2) = 0+0+5 = 5 dp[2][3] = 0+0+6 = 6 dp[3][4] = 0+0+5 = 5 len=3 ： dp[1][3] ： k=1 ： dp[1][1]+dp[2][3] + sum(1,3) = 0+6+9 = 15 k=2 ： dp[1][2]+dp[3][3] + 9 = 5+0+9 = 14 → 取最小值 14 dp[2][4] ： k=2 ： 0+dp[3][4]+sum(2,4)=0+5+7=12 k=3 ： dp[2][3]+0+7=6+0+7=13 → 取 12 len=4 ： dp[1][4] ： k=1 ： 0+dp[2][4]+sum(1,4)=0+12+10=22 k=2 ： dp[1][2]+dp[3][4]+10=5+5+10=20 k=3 ： dp[1][3]+0+10=14+0+10=24 → 最小值为 20 最终结果 dp[1][4] = 20 ，与示例的25不同，说明示例并非最优解。实际上最优顺序为： 合并(2,4) → 代价6 → [ 3,6,1 ] 合并(3,6) → 代价9 → [ 3,7 ] 合并(3,7) → 代价10 → 总代价=6+9+10=25？ 重新验证： 正确最优顺序： 合并(4,1) → 代价5 → [ 3,2,5 ] 合并(3,2) → 代价5 → [ 5,5 ] 合并(5,5) → 代价10 → 总代价=5+5+10=20 因此动态规划结果正确。 总结 本题通过区间DP将问题分解为子区间合并，确保每次合并代价最小。时间复杂度 O(n³)，空间复杂度 O(n²)。