合并石子获得最大得分问题（线性版本） 我将为你讲解"合并石子获得最大得分问题（线性版本）"，这是一个经典的区间动态规划问题。 题目描述 有N堆石子排成一排，每堆石子有一定的质量。现在需要将这些石子合并成一堆。合并的规则是：每次只能合并相邻的两堆石子，合并的代价是这两堆石子的质量之和。合并后的新堆石子质量就是这两堆石子质量之和。目标是找出一种合并顺序，使得合并的总代价最大。 输入格式 第一行：整数N（石子堆数） 第二行：N个整数，表示每堆石子的质量 输出格式 一个整数，表示最大合并代价 解题思路 这个问题可以用区间动态规划来解决。我们需要定义合适的状态和状态转移方程。 步骤1：定义状态 设dp[ i][ j ]表示将第i堆到第j堆石子合并成一堆所能获得的最大代价。 步骤2：状态初始化 当i = j时，只有一堆石子，不需要合并，代价为0 当i < j时，我们需要计算合并这些石子的最大代价 步骤3：前缀和数组 为了快速计算区间[ i,j ]的石子总质量，我们使用前缀和数组prefix： prefix[ i ] = 前i堆石子的质量之和 区间[ i,j]的石子总质量 = prefix[ j] - prefix[ i-1 ] 步骤4：状态转移方程 对于区间[ i,j]，我们可以在位置k（i ≤ k < j）处将其分成两个子区间[ i,k]和[ k+1,j ]。 合并的最大代价 = 左子区间的最大代价 + 右子区间的最大代价 + 整个区间的石子总质量 即：dp[ i][ j] = max(dp[ i][ k] + dp[ k+1][ j] + sum[ i][ j ])，其中k从i到j-1 步骤5：计算顺序 由于大区间依赖于小区间，我们需要按照区间长度从小到大的顺序计算： 先计算长度为2的区间 然后计算长度为3的区间 依此类推，直到计算整个区间[ 1,n ] 详细计算过程 假设有4堆石子，质量分别为：1, 3, 5, 2 步骤1：初始化 dp[ 1][ 1] = 0, dp[ 2][ 2] = 0, dp[ 3][ 3] = 0, dp[ 4][ 4 ] = 0 步骤2：计算前缀和 prefix[ 0 ] = 0 prefix[ 1 ] = 1 prefix[ 2 ] = 1 + 3 = 4 prefix[ 3 ] = 1 + 3 + 5 = 9 prefix[ 4 ] = 1 + 3 + 5 + 2 = 11 步骤3：计算长度为2的区间 dp[ 1][ 2] = dp[ 1][ 1] + dp[ 2][ 2] + sum[ 1][ 2 ] = 0 + 0 + (4-0) = 4 dp[ 2][ 3] = dp[ 2][ 2] + dp[ 3][ 3] + sum[ 2][ 3 ] = 0 + 0 + (9-1) = 8 dp[ 3][ 4] = dp[ 3][ 3] + dp[ 4][ 4] + sum[ 3][ 4 ] = 0 + 0 + (11-4) = 7 步骤4：计算长度为3的区间 dp[ 1][ 3 ]: k=1: dp[ 1][ 1] + dp[ 2][ 3] + sum[ 1][ 3 ] = 0 + 8 + (9-0) = 17 k=2: dp[ 1][ 2] + dp[ 3][ 3] + sum[ 1][ 3 ] = 4 + 0 + 9 = 13 max = 17 dp[ 2][ 4 ]: k=2: dp[ 2][ 2] + dp[ 3][ 4] + sum[ 2][ 4 ] = 0 + 7 + (11-1) = 17 k=3: dp[ 2][ 3] + dp[ 4][ 4] + sum[ 2][ 4 ] = 8 + 0 + 10 = 18 max = 18 步骤5：计算长度为4的区间（整个区间） dp[ 1][ 4 ]: k=1: dp[ 1][ 1] + dp[ 2][ 4] + sum[ 1][ 4 ] = 0 + 18 + 11 = 29 k=2: dp[ 1][ 2] + dp[ 3][ 4] + sum[ 1][ 4 ] = 4 + 7 + 11 = 22 k=3: dp[ 1][ 3] + dp[ 4][ 4] + sum[ 1][ 4 ] = 17 + 0 + 11 = 28 max = 29 最终结果 最大合并代价为29 算法复杂度 时间复杂度：O(n³)，需要三层循环 空间复杂度：O(n²)，用于存储dp数组 关键点总结 区间DP的经典应用，通过分解为子问题求解 前缀和数组用于快速计算区间和 按照区间长度从小到大的顺序计算 状态转移时考虑所有可能的分割点 这个问题的难点在于理解区间动态规划的思想和正确实现状态转移方程。通过这个例子，你可以掌握解决类似区间合并问题的通用方法。