石子合并问题（线性版本） 题目描述 有 N 堆石子排成一排，每堆石子有一定的质量。每次只能合并相邻的两堆石子，合并的代价为这两堆石子的质量之和。合并后的新堆石子质量即为合并前两堆石子质量之和，且新堆与相邻堆的位置关系保持不变。重复合并，直到所有石子合并成一堆。问将 N 堆石子合并成一堆的最小总代价是多少？ 例如，有 4 堆石子，质量依次为 [ 1, 3, 5, 2 ]。 一种合并方案： 合并前两堆（质量1和3），代价=1+3=4，得到新堆质量4，石子堆变为[ 4, 5, 2 ]； 合并后两堆（质量5和2），代价=5+2=7，得到新堆质量7，石子堆变为[ 4, 7 ]； 合并最后两堆（质量4和7），代价=4+7=11，总代价=4+7+11=22。 但可能存在更优的合并顺序使得总代价更小。 解题过程 1. 问题分析 关键点：每次合并相邻两堆，且合并代价与当前堆的质量有关。 最终状态：所有堆合并为一堆。 决策：在某一区间内，选择最后一次合并的位置，将区间分成左右两部分，分别合并成两堆后再合并。 这符合区间动态规划的特征：问题可以分解为更小的子区间问题。 2. 定义状态 设 dp[i][j] 表示将第 i 堆到第 j 堆石子合并成一堆的最小代价。 目标：求 dp[1][N] （这里下标从1开始）。 3. 状态转移方程 考虑区间 [i, j] 的最后一次合并：一定是将 [i, k] 合并的一堆与 [k+1, j] 合并的一堆合并（i ≤ k < j）。 合并 [i, k] 的代价是 dp[i][k] ，合并 [k+1, j] 的代价是 dp[k+1][j] 。 最后合并这两堆的代价是区间 [i, j] 的总石子质量（因为最后一步合并的代价等于两堆质量之和，而这两堆的质量分别是 [i, k] 的总质量和 [k+1, j] 的总质量）。 区间总和可以用前缀和快速计算：设 prefix[i] 表示前 i 堆石子质量之和，则 sum(i, j) = prefix[j] - prefix[i-1] 。 转移方程： 边界条件： dp[i][i] = 0 （单独一堆不需要合并）。 4. 计算顺序 区间 DP 通常按区间长度从小到大计算。 先算所有长度为 2 的区间，再算长度为 3 的区间，直到长度为 N。 5. 示例计算 石子质量 = [ 1, 3, 5, 2 ]，N=4。 前缀和 prefix: [ 0, 1, 4, 9, 11]（prefix[ 0]=0, prefix[ 1]=1, prefix[ 2]=4, prefix[ 3]=9, prefix[ 4 ]=11）。 长度=1: dp[ 1][ 1]=0, dp[ 2][ 2]=0, dp[ 3][ 3]=0, dp[ 4][ 4 ]=0。 长度=2: dp[ 1][ 2] = dp[ 1][ 1] + dp[ 2][ 2 ] + sum(1,2) = 0+0+(3+1)=4 dp[ 2][ 3 ] = 0+0+(3+5)=8 dp[ 3][ 4 ] = 0+0+(5+2)=7 长度=3: dp[ 1][ 3 ]: k=1: dp[ 1][ 1]+dp[ 2][ 3 ]+sum(1,3)=0+8+(1+3+5)=17 k=2: dp[ 1][ 2]+dp[ 3][ 3 ]+sum(1,3)=4+0+9=13 → min=13 dp[ 2][ 4 ]: k=2: dp[ 2][ 2]+dp[ 3][ 4 ]+sum(2,4)=0+7+(3+5+2)=17 k=3: dp[ 2][ 3]+dp[ 4][ 4 ]+sum(2,4)=8+0+10=18 → min=17 长度=4: dp[ 1][ 4 ]: k=1: dp[ 1][ 1]+dp[ 2][ 4 ]+sum(1,4)=0+17+11=28 k=2: dp[ 1][ 2]+dp[ 3][ 4 ]+sum(1,4)=4+7+11=22 k=3: dp[ 1][ 3]+dp[ 4][ 4 ]+sum(1,4)=13+0+11=24 min=22 最小总代价 = 22。 6. 复杂度 状态数 O(N²)，每个状态枚举 k 为 O(N)，总复杂度 O(N³)。 可用四边形不等式优化到 O(N²)，但这里不展开。