区间动态规划例题：合并石子获得最大得分问题 题目描述 有一排石子堆，每堆石子有一定的价值。游戏规则是：每次只能合并相邻的两堆石子，合并的得分是新堆的石子总数，合并后新堆的价值是原两堆价值之和。重复合并直到只剩一堆石子。求所有合并方式中能获得的最大总得分。 例如：石子堆价值为 [ 3, 4, 2 ] 先合并前两堆：得分为 3+4=7，新堆为 [ 7, 2 ]；再合并得 7+2=9，总得分 7+9=16 先合并后两堆：得分为 4+2=6，新堆为 [ 3, 6 ]；再合并得 3+6=9，总得分 6+9=15 最大得分为 16 解题思路 问题分析 ：每次合并相邻堆的得分是两堆价值之和，而合并顺序会影响后续得分。区间动态规划适合处理这种相邻合并问题。 状态定义 ：设 dp[i][j] 表示合并第 i 到第 j 堆石子能获得的最大得分（i≤j）。 区间分割 ：合并 [ i,j] 时，最后一次合并一定是将 [ i,k] 和 [ k+1,j] 两组合并后的堆再合并。因此枚举分割点 k（i≤k <j），计算得分。 得分计算 ：合并 [ i,j] 的得分等于合并左半部分得分 dp[i][k] + 合并右半部分得分 dp[k+1][j] + 当前合并的代价（即 [ i,j ] 的总价值，用前缀和快速计算）。 边界条件 ：单堆石子（i=j）时得分为 0（无需合并）。 计算顺序 ：按区间长度从小到大计算。 逐步求解 以石子堆 [ 3,4,2 ] 为例： 前缀和预处理 ：设 prefix[i] 为前 i 堆价值和（从1索引），方便求区间和。 堆索引：1:3, 2:4, 3:2 prefix[ 0]=0, prefix[ 1]=3, prefix[ 2]=7, prefix[ 3 ]=9 区间 [ l,r] 和 = prefix[ r] - prefix[ l-1 ] DP 表初始化 （区间长度 len=1）： dp[ 1][ 1]=0, dp[ 2][ 2]=0, dp[ 3][ 3 ]=0（单堆合并得分为0） 区间长度 len=2 ： 合并 [ 1,2 ]：k=1（分割点唯一） dp[ 1][ 2] = dp[ 1][ 1] + dp[ 2][ 2 ] + (3+4) = 0+0+7 = 7 合并 [ 2,3 ]：k=2 dp[ 2][ 3] = dp[ 2][ 2] + dp[ 3][ 3 ] + (4+2) = 0+0+6 = 6 区间长度 len=3 ： 合并 [ 1,3 ]：枚举 k=1 或 k=2 k=1：得分 = dp[ 1][ 1] + dp[ 2][ 3 ] + (3+4+2) = 0+6+9 = 15 k=2：得分 = dp[ 1][ 2] + dp[ 3][ 3 ] + 9 = 7+0+9 = 16 取最大值：dp[ 1][ 3 ] = 16 结果 ：最大总得分为 dp[ 1][ 3 ] = 16 关键点 合并得分依赖子区间最优解，符合最优子结构。 前缀和优化避免重复计算区间和。 时间复杂度 O(n³)，空间复杂度 O(n²)。