合并石子获得最小得分问题（线性版本） 题目描述 有N堆石子排成一排，每堆石子的数量用一个数组 stones 表示，其中 stones[i] 表示第i堆石子的数量。每次只能合并相邻的两堆石子，合并的代价为这两堆石子的数量之和。合并后新堆的石子数量为两堆之和，并与其他相邻堆继续排成一行。重复合并相邻两堆，直到所有石子合并成一堆。求将全部石子合并成一堆的最小总代价。 解题过程 1. 问题分析 这是一个经典的区间动态规划问题。关键在于每次合并相邻两堆，且合并代价为两堆石子数之和。最终目标是找到一种合并顺序，使得总代价最小。例如，对于石子堆 [1, 2, 3] ，如果先合并前两堆（代价=1+2=3，新堆为 [3, 3] ），再合并剩余两堆（代价=3+3=6），总代价=3+6=9；如果先合并后两堆（代价=2+3=5，新堆为 [1, 5] ），再合并（代价=1+5=6），总代价=5+6=11。最小代价为9。 2. 定义状态 设 dp[i][j] 表示将第i堆到第j堆石子合并成一堆的最小代价（i和j从0开始计数）。目标是求 dp[0][n-1] ，其中n为石子堆数。 3. 状态转移方程 考虑最后一次合并：在合并区间 [i, j] 时，一定是将 [i, k] 和 [k+1, j] 两堆合并（i ≤ k < j）。合并代价为 dp[i][k] + dp[k+1][j] + sum(i, j) ，其中 sum(i, j) 是区间 [i, j] 的石子总数（即最后一次合并的代价）。因此： dp[i][j] = min(dp[i][k] + dp[k+1][j] + sum(i, j)) ，对所有k满足i ≤ k < j。 注意：当i = j时，只有一堆石子，无需合并，代价为0。 4. 计算前缀和优化 为了快速计算 sum(i, j) ，可以预处理前缀和数组 prefix ，其中 prefix[j] 表示前j堆石子总数（j从0开始）。则 sum(i, j) = prefix[j] - (i > 0 ? prefix[i-1] : 0) 。 5. 递推顺序 由于计算 dp[i][j] 需要依赖更短的区间（即 dp[i][k] 和 dp[k+1][j] ），我们按区间长度L从小到大递推： 先计算所有长度为1的区间（即单堆，代价为0）。 再计算长度为2的区间（相邻两堆合并），然后长度为3，直到长度为n。 6. 示例计算 以 stones = [1, 2, 3] 为例： 前缀和 prefix = [1, 3, 6] 。 初始化：所有 dp[i][i] = 0 。 长度L=2： dp[0][1] = min(dp[0][0] + dp[1][1] + sum(0,1)) = 0 + 0 + (3-0) = 3 。 dp[1][2] = 0 + 0 + (6-3) = 3 。 长度L=3： k=0: dp[0][0] + dp[1][2] + sum(0,2) = 0 + 3 + 6 = 9 。 k=1: dp[0][1] + dp[2][2] + sum(0,2) = 3 + 0 + 6 = 9 。 dp[0][2] = min(9, 9) = 9 。 最终最小代价为9。 7. 复杂度分析 时间复杂度：O(n³)，需要三层循环（区间长度、起点、分割点）。 空间复杂度：O(n²)，用于存储dp表。