石子合并问题（线性版本，最小得分） 题目描述： 有N堆石子排成一排，每堆石子有一定的数量。现要将所有石子合并成一堆，合并的规则是每次只能合并相邻的两堆石子，合并的代价为这两堆石子的数量之和。经过N-1次合并后，所有石子合并成一堆，求所有合并方案中总代价的最小值。 解题过程： 问题分析： 我们需要将一排石子合并成一堆，每次只能合并相邻的两堆 每次合并的代价是这两堆石子的数量之和 目标是找到合并顺序使得总代价最小 这是一个典型的区间动态规划问题 状态定义： 定义dp[ i][ j ]表示合并第i堆到第j堆石子的最小代价 状态转移方程： 对于区间[ i, j]，我们可以选择在位置k(i ≤ k < j)处将区间分成两部分： 先合并[ i, k ] 再合并[ k+1, j ] 最后将这两个大堆合并 因此状态转移方程为： dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j] + sum[ i][ j])，其中i ≤ k < j 其中sum[ i][ j ]表示从第i堆到第j堆石子的总数 边界条件： 当i = j时，dp[ i][ j ] = 0（只有一堆石子，不需要合并） 当j = i+1时，dp[ i][ j] = stones[ i] + stones[ j ]（相邻两堆直接合并） 计算顺序： 由于大区间依赖于小区间，我们需要按照区间长度从小到大计算： 先计算长度为2的区间 再计算长度为3的区间 依此类推，直到计算整个区间[ 1, n ] 前缀和优化： 为了快速计算sum[ i][ j ]，我们可以预处理前缀和数组prefix： prefix[ i] = stones[ 1] + stones[ 2] + ... + stones[ i ] 那么sum[ i][ j] = prefix[ j] - prefix[ i-1 ] 算法步骤： 步骤1：读取输入，n堆石子 步骤2：计算前缀和数组prefix 步骤4：初始化dp数组，dp[ i][ i ] = 0 步骤5：按区间长度len从2到n遍历： 对于每个起点i从1到n-len+1： 计算终点j = i + len - 1 初始化dp[ i][ j ]为无穷大 对于每个分割点k从i到j-1： 计算代价 = dp[ i][ k] + dp[ k+1][ j] + prefix[ j] - prefix[ i-1 ] 更新dp[ i][ j ]的最小值 步骤6：返回dp[ 1][ n ] 时间复杂度：O(n³) 空间复杂度：O(n²) 示例： 输入：stones = [ 3, 4, 2, 1 ] 计算过程： 先计算所有长度为2的区间： dp[ 1][ 2 ] = 3+4 = 7 dp[ 2][ 3 ] = 4+2 = 6 dp[ 3][ 4 ] = 2+1 = 3 再计算长度为3的区间： dp[ 1][ 3] = min(dp[ 1][ 1]+dp[ 2][ 3], dp[ 1][ 2]+dp[ 3][ 3 ]) + 3+4+2 = min(0+6, 7+0) + 9 = min(6,7)+9 = 15 dp[ 2][ 4] = min(dp[ 2][ 2]+dp[ 3][ 4], dp[ 2][ 3]+dp[ 4][ 4 ]) + 4+2+1 = min(0+3, 6+0) + 7 = min(3,6)+7 = 10 最后计算整个区间： dp[ 1][ 4] = min(dp[ 1][ 1]+dp[ 2][ 4], dp[ 1][ 2]+dp[ 3][ 4], dp[ 1][ 3]+dp[ 4][ 4 ]) + 3+4+2+1 = min(0+10, 7+3, 15+0) + 10 = min(10,10,15)+10 = 20 最终最小代价为20。