dp[i][j] = min{ dp[i][k] + dp[k+1][j] + sum(i, j) }  对 k 从 i 到 j-1

合并相邻石子堆的最小成本问题（线性版） 问题描述 有 n 堆石子排成一行，其中第 i 堆有石子 stones[i] 个。现在你需要将这些石子堆合并成一堆，合并规则如下： 每次只能合并 相邻 的两堆石子。 合并的成本为这两堆石子的石子数之和。 合并后，这两堆石子合并为一堆，其石子数为合并前两堆石子数之和，并占据原来的位置。 你需要找到将这一行石子堆合并成一堆的 最小总成本 。 例如： 输入： stones = [3, 2, 4, 1] 输出： 20 解释： 一种最优合并顺序为： 合并 2 和 4（成本 2+4=6），数组变为 [ 3, 6, 1 ] 合并 3 和 6（成本 3+6=9），数组变为 [ 9, 1 ] 合并 9 和 1（成本 9+1=10），总成本 6+9+10=25（注意这不是最优）。 实际上最优顺序是： 合并 3 和 2（成本 5），数组变为 [ 5, 4, 1 ] 合并 4 和 1（成本 5），数组变为 [ 5, 5 ] 合并 5 和 5（成本 10），总成本 5+5+10=20。 解题思路 这是一个经典的区间动态规划问题。 将合并过程看作对区间 [i, j] 内的石子堆进行合并，最后一步一定是将某个左区间 [i, k] 和右区间 [k+1, j] 合并，合并成本为 sum(i, j) （区间内石子总数）。 我们需要枚举最后一个分界点 k ，从而找到最小成本。 定义状态 设 dp[i][j] 表示将区间 [i, j] 内的石子堆合并成一堆的最小成本（ i 和 j 从 0 开始）。 当 i == j 时，只有一堆石子，不需要合并，成本为 0。 状态转移方程 对于 i < j ，考虑最后一次合并发生在分界点 k （ i ≤ k < j ）： 先合并 [i, k] 为 1 堆，成本为 dp[i][k] 。 再合并 [k+1, j] 为 1 堆，成本为 dp[k+1][j] 。 最后合并这两堆，成本为 sum(i, j) （即区间 [i, j] 的石子总数）。 因此： 其中 sum(i, j) 可以通过前缀和快速计算。 计算顺序 由于大区间依赖于小区间，我们需要按区间长度 len 从小到大计算。 先计算所有长度为 1 的区间（成本 0）。 再计算长度为 2, 3, ..., n 的区间。 最终答案 dp[0][n-1] 就是整个数组合并成一堆的最小成本。 示例计算 （ stones = [3, 2, 4, 1] ，n=4） 前缀和数组 prefix ： prefix[0]=0, prefix[1]=3, prefix[2]=5, prefix[3]=9, prefix[4]=10 。 sum(i, j) = prefix[j+1] - prefix[i] 。 初始化： dp[i][i] = 0 。 长度 len=2： [ 0,1]：k=0， dp[0][1] = dp[0][0] + dp[1][1] + sum(0,1) = 0+0+5=5 。 [ 1,2 ]：sum=2+4=6 → dp=6。 [ 2,3 ]：sum=4+1=5 → dp=5。 长度 len=3： [ 0,2 ]： k=0： dp[0][0]+dp[1][2]+sum(0,2)=0+6+9=15 。 k=1： dp[0][1]+dp[2][2]+9=5+0+9=14 。 min=14。 [ 1,3 ]： k=1： dp[1][1]+dp[2][3]+sum(1,3)=0+5+7=12 。 k=2： dp[1][2]+dp[3][3]+7=6+0+7=13 。 min=12。 长度 len=4：[ 0,3 ]： k=0： dp[0][0]+dp[1][3]+sum(0,3)=0+12+10=22 。 k=1： dp[0][1]+dp[2][3]+10=5+5+10=20 。 k=2： dp[0][2]+dp[3][3]+10=14+0+10=24 。 min=20。 所以最终答案为 20。 复杂度分析 状态数：O(n²)。 每个状态枚举分割点 k：O(n)。 总时间复杂度 O(n³)，空间复杂度 O(n²)。 优化提示 对于某些特殊性质（如石子重量非负），可以用四边形不等式优化到 O(n²)，但一般 O(n³) 解法在 n ≤ 200 时可行。