环形石子合并问题（最大得分版本） 问题描述： 有n堆石子排成一个环形，每堆石子有一定的数量。现在要将这些石子合并成一堆，合并规则是每次只能合并相邻的两堆，合并的得分是新堆的石子数。请计算合并的最大总得分。 解题过程： 问题分析： 石子环形排列意味着第1堆和第n堆是相邻的 需要将环形问题转化为线性问题处理 合并得分是每次合并后新堆的石子数 目标是最大化所有合并步骤的得分总和 解题思路： 将环形石子复制一份接在原数组后面，形成长度为2n的线性数组 在长度为2n的数组上使用区间DP求解 最终答案在长度为n的所有区间中取最大值 状态定义： 定义dp[ i][ j]表示合并区间[ i,j ]内的石子所能获得的最大得分 状态转移方程： 对于区间[ i,j]，枚举分割点k（i ≤ k < j）： dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j] + sum[ i][ j ]) 其中sum[ i][ j]表示区间[ i,j ]内石子的总数 前缀和预处理： 为了快速计算区间和，先计算前缀和数组prefix： prefix[ 0 ] = 0 prefix[ i] = prefix[ i-1] + stones[ i-1 ] sum[ i][ j] = prefix[ j+1] - prefix[ i ] 算法步骤： 步骤1：输入石子数量数组stones，长度为n 步骤2：构建长度为2n的扩展数组extended_ stones 步骤3：计算扩展数组的前缀和prefix 步骤4：初始化dp数组为0 步骤5：按区间长度从小到大遍历： 长度len从2到n（因为至少要合并两堆） 左端点i从0到2n-len 右端点j = i + len - 1 枚举分割点k从i到j-1 更新dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j] + sum[ i][ j ]) 步骤6：在长度为n的所有区间中找出最大得分 复杂度分析： 时间复杂度：O(n³)，需要三重循环 空间复杂度：O(n²)，用于存储dp数组 示例演示： 假设石子堆为[ 3,4,5 ]： 扩展数组为[ 3,4,5,3,4,5 ] 计算所有长度为3的区间得分 取最大值作为最终答案 这种环形处理的方法可以确保考虑到所有可能的合并顺序，从而找到最大得分。