环形石子合并问题（最大得分版本） 问题描述： 有n堆石子排成一个环形，每堆石子有一定的数量。现在要将这些石子合并成一堆，合并规则是每次只能合并相邻的两堆石子，合并的得分是新堆的石子数。请计算合并的最大总得分。 解题过程： 让我们通过一个具体例子来理解：石子堆为[ 3,4,5,2 ] 问题分析： 环形结构意味着我们需要考虑所有可能的起点 每次合并相邻两堆，得分是合并堆的石子总数 目标是最大化总得分 关键思路： 将环形问题转化为线性问题。对于环形数组，我们可以通过复制数组来模拟所有可能的起点情况。 状态定义： 设dp[ i][ j ]表示合并从第i堆到第j堆石子所能获得的最大得分。 状态转移方程： 对于区间[ i,j ]，我们可以枚举最后一次合并的位置k： dp[ i][ j] = max(dp[ i][ k] + dp[ k+1][ j] + sum[ i][ j ]) 其中sum[ i][ j ]表示从i到j的石子总数 具体步骤： 步骤1：预处理前缀和 原始数组：3,4,5,2 环形处理：将数组复制一份得到[ 3,4,5,2,3,4,5,2 ] 计算前缀和prefix，prefix[ i ]表示前i个元素的和 步骤2：初始化DP表 对于单个石子堆，dp[ i][ i ] = 0（不需要合并） 步骤3：按区间长度递推 从长度为2开始，逐步计算到长度为n： 长度为2时： dp[ 0][ 1 ] = 3+4 = 7 dp[ 1][ 2 ] = 4+5 = 9 dp[ 2][ 3 ] = 5+2 = 7 dp[ 3][ 4 ] = 2+3 = 5 长度为3时： 以[ 0,2 ]为例： 分割点k=1：dp[ 0][ 1]+dp[ 2][ 2]+sum[ 0,2 ] = 7+0+12 = 19 dp[ 0][ 2 ] = 19 长度为4时（完整环形）： 我们需要考虑所有可能的起点： 起点0：dp[ 0][ 3 ] 起点1：dp[ 1][ 4 ]（在扩展数组中） 起点2：dp[ 2][ 5 ] 起点3：dp[ 3][ 6 ] 最终答案： 在所有的起点对应的dp[ i][ i+n-1 ]中取最大值 时间复杂度：O(n³)，空间复杂度：O(n²) 这个算法的核心在于通过复制数组将环形问题转化为线性问题，然后使用标准的区间DP方法求解。