合并石子获得最小得分问题（线性版本） 题目描述 有N堆石子排成一排，每堆石子有一定的重量（正整数）。现在需要将这些石子合并成一堆，每次合并只能将相邻的两堆合并成一堆，合并的代价是这两堆石子的重量之和。经过N-1次合并后，石子合并成一堆。请设计一个算法，找出一种合并顺序，使得总合并代价最小。 例如，有4堆石子，重量分别为[ 1, 2, 3, 4 ]。 一种合并方式： 先合并前两堆（代价1+2=3），石子堆变为[ 3, 3, 4 ] 再合并前两堆（代价3+3=6），石子堆变为[ 6, 4 ] 最后合并两堆（代价6+4=10），总代价=3+6+10=19 另一种合并方式： 先合并中间两堆（代价2+3=5），石子堆变为[ 1, 5, 4 ] 再合并后两堆（代价5+4=9），石子堆变为[ 1, 9 ] 最后合并两堆（代价1+9=10），总代价=5+9+10=24 我们的目标是找到总代价最小的合并顺序。 解题过程 问题分析 这是一个典型的区间动态规划问题，因为每次操作影响的是连续的石子堆。 关键点：最后一次合并一定是将某个前缀区间和后缀区间合并，而这两个区间本身也是通过最优方式合并得到的。 定义状态 设 dp[i][j] 表示将第i堆到第j堆石子合并成一堆所需的最小代价（i ≤ j）。 我们的目标是求 dp[1][N] （假设石子堆编号从1开始）。 状态转移方程 考虑如何得到 dp[i][j] ：在合并区间[ i, j]时，最后一次合并一定是将[ i, k]和[ k+1, j]这两堆合并（i ≤ k < j）。 合并代价是[ i, k]的总重量加上[ k+1, j]的总重量，即整个区间[ i, j ]的石子总重量。 因此， dp[i][j] = min(dp[i][k] + dp[k+1][j]) + sum(i, j) ，其中k从i遍历到j-1。 注意：当i = j时，只有一堆石子，不需要合并，代价为0。 计算区间和 为了快速计算任意区间[ i, j]的石子总重量，我们可以预先计算前缀和数组 prefix ： prefix[0] = 0 prefix[i] = 石子1到石子i的重量和 那么 sum(i, j) = prefix[j] - prefix[i-1] 确定计算顺序 由于 dp[i][j] 依赖于更短的区间（即区间长度更小的状态），我们需要按区间长度从小到大计算。 先计算所有长度为1的区间（即单堆石子，代价为0），然后计算长度为2的区间，接着长度为3，直到长度为N。 算法步骤 输入：石子重量数组 stones[1..N] 初始化： 创建 dp[N+1][N+1] ，初始化为0（或一个大数，但 dp[i][i] = 0 ） 计算前缀和数组 prefix[0..N] 循环区间长度 len 从2到N（长度为1时代价为0，无需计算）： 循环区间起点 i 从1到 N-len+1 ： 区间终点 j = i + len - 1 初始化 dp[i][j] 为一个很大的数（例如INT_ MAX） 循环分割点 k 从 i 到 j-1 ： 计算合并代价 cost = dp[i][k] + dp[k+1][j] + prefix[j] - prefix[i-1] 如果 cost < dp[i][j] ，则更新 dp[i][j] = cost 输出 dp[1][N] 示例演示 石子重量[ 1, 2, 3, 4 ]，N=4 前缀和 prefix = [0, 1, 3, 6, 10] 计算过程： 长度2： [ 1,2]: dp[ 1][ 2] = min( dp[ 1][ 1]+dp[ 2][ 2 ] ) + sum(1,2) = 0+0+3 = 3 [ 2,3]: dp[ 2][ 3 ] = 0+0+5 = 5 [ 3,4]: dp[ 3][ 4 ] = 0+0+7 = 7 长度3： [ 1,3]: k=1: dp[ 1][ 1]+dp[ 2][ 3 ]+sum(1,3)=0+5+6=11 k=2: dp[ 1][ 2]+dp[ 3][ 3 ]+sum(1,3)=3+0+6=9 → min=9 [ 2,4 ]: k=2: 0+7+9=16; k=3: 5+0+9=14 → min=14 长度4：[ 1,4 ] k=1: dp[ 1][ 1]+dp[ 2][ 4 ]+sum(1,4)=0+14+10=24 k=2: dp[ 1][ 2]+dp[ 3][ 4 ]+sum(1,4)=3+7+10=20 k=3: dp[ 1][ 3]+dp[ 4][ 4 ]+sum(1,4)=9+0+10=19 → 最小代价19 通过这种自底向上的计算方式，我们就能找到合并石子的最小代价。这个算法的时间复杂度是O(N³)，空间复杂度是O(N²)。