石子合并问题（相邻合并，最大得分版本） 题目描述： 有N堆石子排成一排，每堆石子有一定的数量。现要将所有石子合并成一堆，合并的规则是：每次只能选择相邻的两堆石子合并成一堆，合并的代价是这两堆石子的数量之和。经过N-1次合并后，所有石子合并成一堆。不同的合并顺序会得到不同的总代价，请找出一种合并顺序，使得总合并代价最大。 解题过程： 问题分析 我们需要将一排石子合并成一堆，每次合并相邻两堆，目标是最大化总合并代价。这与最小代价版本相反，但解题思路相似。 状态定义 定义dp[ i][ j ]表示将第i堆到第j堆石子合并成一堆所能获得的最大代价，其中1 ≤ i ≤ j ≤ N。 状态转移方程 对于区间[ i,j]，我们可以通过最后一次合并的位置k来划分，其中i ≤ k < j： 最后一次合并是将[ i,k]和[ k+1,j ]这两大堆合并 合并代价是[ i,k]的总石子和[ k+1,j ]的总石子之和 而[ i,k ]的总石子数可以用前缀和快速计算 因此状态转移方程为： dp[ i][ j] = max(dp[ i][ k] + dp[ k+1][ j] + sum[ i][ j])，其中i ≤ k < j 其中sum[ i][ j ]表示从第i堆到第j堆的石子总数。 边界条件 当i = j时，只有一堆石子，不需要合并，代价为0：dp[ i][ i ] = 0 当i > j时，无效区间，不考虑 计算顺序 由于大区间依赖于小区间，我们需要按照区间长度从小到大计算： 先计算长度为1的区间（单堆石子） 然后计算长度为2的区间 依此类推，直到计算长度为N的区间 具体实现步骤 步骤1：计算前缀和数组prefix，其中prefix[ i ]表示前i堆石子的总和 步骤2：初始化dp数组，所有dp[ i][ i ] = 0 步骤3：按区间长度len从2到N遍历： 对于每个起始位置i从1到N-len+1： 令j = i + len - 1 初始化dp[ i][ j ] = -∞ 对于每个分割点k从i到j-1： cost = dp[ i][ k] + dp[ k+1][ j] + (prefix[ j] - prefix[ i-1 ]) dp[ i][ j] = max(dp[ i][ j ], cost) 步骤4：dp[ 1][ N ]就是最大合并代价 时间复杂度 三重循环：O(N³) 空间复杂度：O(N²) 示例验证 假设有4堆石子：[ 4, 5, 9, 4 ] 前缀和：[ 0, 4, 9, 18, 22 ] 计算过程： len=2: dp[ 1][ 2]=4+5=9, dp[ 2][ 3]=5+9=14, dp[ 3][ 4 ]=9+4=13 len=3: dp[ 1][ 3 ]=max(9+14+18, 0+13+18)=max(41,31)=41 dp[ 2][ 4 ]=max(14+13+13, 0+4+13)=max(40,17)=40 len=4: dp[ 1][ 4 ]=max(9+40+22, 41+13+22, 0+54+22)=max(71,76,76)=76 最大合并代价为76。