其中 `sum(i, j)` 是 `stones[i] + ... + stones[j]`，可通过前缀和计算：`prefix[j] - prefix[i-1]`。  

石子合并问题（相邻合并，最大得分版本） 题目描述 给定一排 n 堆石子，每堆石子的数量用一个数组 stones 表示（ stones[i] 表示第 i 堆的石子数）。每次操作可以选择相邻的两堆石子合并成一堆，合并的得分为新堆的石子数（即两堆石子数之和）。重复操作直到所有石子合并成一堆，求所有合并方式中能够获得的最大总得分。 解题过程 问题分析 合并过程是相邻合并，每次合并后区间会变化，且总得分与合并顺序有关。 关键点：最后一次合并的得分一定是所有石子总数，但中间过程的合并顺序会影响总得分。 目标：通过合理安排合并顺序，使得中间合并过程的得分总和最大。 状态定义 设 dp[i][j] 表示将第 i 堆到第 j 堆石子合并成一堆所能获得的最大总得分（注意： dp[i][j] 不包含合并前区间内石子本身的总和，仅代表合并过程中产生的得分总和）。 为了快速计算任意区间的石子总数，预处理前缀和数组 prefix ，其中 prefix[k] 表示前 k 堆石子总数（索引从 1 开始方便计算，实际代码中需调整）。 状态转移方程 考虑区间 [i, j] 的最后一次合并：一定是将 [i, k] 和 [k+1, j] 两堆合并（ i ≤ k < j ）。 合并区间 [i, j] 的得分 = 合并 [i, k] 的得分 + 合并 [k+1, j] 的得分 + 本次合并的得分（即区间 [i, j] 的石子总数）。 因此： \[ dp[ i][ j] = \max_ {i \le k < j} \{ dp[ i][ k] + dp[ k+1][ j ] \} + \text{sum}(i, j) \] 其中 sum(i, j) 是 stones[i] + ... + stones[j] ，可通过前缀和计算： prefix[j] - prefix[i-1] 。 初始化与边界 单个石子堆不需要合并： dp[i][i] = 0 （合并得分为 0）。 区间长度 len 从 2 开始枚举到 n 。 计算顺序 按区间长度从小到大计算，确保计算 dp[i][j] 时，其子区间 dp[i][k] 和 dp[k+1][j] 已计算完毕。 举例说明 假设 stones = [3, 4, 5] ： 前缀和 prefix = [0, 3, 7, 12] （索引 0 为 0，索引 1~3 对应石子堆）。 区间长度 2： dp[1][2] = dp[1][1] + dp[2][2] + sum(1,2) = 0 + 0 + 7 = 7 dp[2][3] = 0 + 0 + 9 = 9 区间长度 3： 枚举 k=1 ： dp[1][1] + dp[2][3] + sum(1,3) = 0 + 9 + 12 = 21 枚举 k=2 ： dp[1][2] + dp[3][3] + sum(1,3) = 7 + 0 + 12 = 19 取最大值： dp[1][3] = 21 最大总得分为 21。 总结 核心是通过区间 DP 枚举所有合并顺序，利用前缀和优化区间和计算。 注意：本题与“最小得分版本”的区别仅在于取最大值而非最小值，但状态转移结构相同。