石子合并问题（线性版本）

题目描述
有 N 堆石子排成一排，每堆石子有一定的质量（用整数表示）。每次只能合并相邻的两堆石子，合并的代价为这两堆石子的质量之和。合并后的新堆石子质量是这两堆石子质量之和，且新堆与剩余石子仍然排成一排。重复合并相邻两堆，直到只剩下一堆石子为止。求将 N 堆石子合并成一堆的最小总代价。

例如，有 4 堆石子，质量依次为 [4, 2, 3, 1]。一种合并方式为：

1. 合并质量 2 和 3 的石子堆（代价 5），石子堆变为 [4, 5, 1]
2. 合并质量 4 和 5 的石子堆（代价 9），石子堆变为 [9, 1]
3. 合并质量 9 和 1 的石子堆（代价 10），总代价为 5 + 9 + 10 = 24。
   但可能存在总代价更小的合并顺序。

解题过程

1. 定义状态
   设 dp[i][j] 表示将第 i 堆到第 j 堆石子合并成一堆的最小代价。目标是求 dp[1][N]（假设石子堆编号从 1 到 N）。

2. 状态转移方程
   考虑最后一次合并操作：在合并第 i 堆到第 j 堆石子时，最后一步一定是将 [i, k] 和 [k+1, j] 两堆合并（其中 i ≤ k < j）。

   • 合并 [i, k] 的代价为 dp[i][k]
   • 合并 [k+1, j] 的代价为 dp[k+1][j]
   • 最后一步合并的代价为第 i 到 j 堆石子总质量（即 sum[i][j]）
     因此，转移方程为：

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

3. 初始化与预处理

   • 单堆石子不需要合并，代价为 0：dp[i][i] = 0。
   • 为快速计算 sum[i][j]，预处理前缀和数组 prefix：
     prefix[0] = 0, prefix[i] = stones[1] + stones[2] + ... + stones[i]
     则 sum[i][j] = prefix[j] - prefix[i-1]。

4. 计算顺序
   由于 dp[i][j] 依赖于更短的区间，需按区间长度 len 从小到大计算：

   • 外层循环遍历区间长度 len = 2 to N
   • 内层循环遍历区间起点 i = 1 to N-len+1，终点 j = i+len-1
   • 内层枚举分割点 k = i to j-1，更新 dp[i][j]。

5. 示例计算
   石子质量 [4, 2, 3, 1]（N=4），前缀和 [0,4,6,9,10]：

   • len=2：
     dp[1][2] = dp[1][1] + dp[2][2] + (4+2) = 0+0+6 = 6
dp[2][3] = 0+0+5=5, dp[3][4]=0+0+4=4
   • len=3：
     dp[1][3] = min( dp[1][1]+dp[2][3]+9, dp[1][2]+dp[3][3]+9 ) = min(0+5+9, 6+0+9)=min(14,15)=14
dp[2][4] = min( dp[2][2]+dp[3][4]+6, dp[2][3]+dp[4][4]+6 ) = min(0+4+6, 5+0+6)=min(10,11)=10
   • len=4：
     dp[1][4] = min( k=1: dp[1][1]+dp[2][4]+10, k=2: dp[1][2]+dp[3][4]+10, k=3: dp[1][3]+dp[4][4]+10 )
= min(0+10+10, 6+4+10, 14+0+10) = min(20,20,24) = 20
     最小总代价为 20。

关键点

• 区间 DP 通过枚举分割点将大区间拆分为两个已计算的小区间。
• 前缀和优化避免重复计算区间和。
• 需确保计算顺序满足子问题先求解。