环形石子合并的最大得分问题 题目描述 有N堆石子排成一个环形，每堆石子的数量用数组stones表示，其中stones[ i ]表示第i堆石子的数量。每次操作可以将相邻的两堆石子合并为一堆，合并的得分等于这两堆石子的数量之和。合并后得到的新石子堆的数量也是这两堆石子数量之和。游戏一直进行到只剩下一堆石子为止。请计算能获得的最大总得分。 解题过程 1. 问题分析 这是一个经典的区间动态规划问题，但有一个关键变化：石子排列成环形而不是线性。这意味着我们需要考虑环形结构带来的循环相邻关系。 2. 环形转线性 处理环形问题的常用技巧是将原数组复制一份接在后面，形成一个长度为2N的线性数组。这样，原环形数组中所有可能的连续区间都对应新线性数组中的某个长度为N的区间。 3. 状态定义 定义dp[ i][ j ]表示合并从第i堆到第j堆石子所能获得的最大得分，其中1 ≤ i ≤ j ≤ 2N。 4. 状态转移方程 对于区间[ i,j]，我们可以枚举最后一次合并的位置k（i ≤ k < j），将区间分成[ i,k]和[ k+1,j ]两部分： dp[ i][ j] = max(dp[ i][ k] + dp[ k+1][ j ] + sum(i,j)) 其中sum(i,j)表示从i到j的石子总数，可以通过前缀和数组快速计算。 5. 初始化 单个石子堆不需要合并：dp[ i][ i ] = 0 计算前缀和数组prefix，其中prefix[ i ]表示前i堆石子的总和 6. 计算顺序 按区间长度从小到大计算： 先计算长度为2的区间 然后计算长度为3的区间 ... 最后计算长度为N的区间 7. 寻找最终答案 由于是环形结构，最大得分可能是从任意位置开始的长度为N的区间： 答案 = max(dp[ i][ i+N-1 ])，其中1 ≤ i ≤ N 8. 示例说明 假设有4堆石子排成环形：[ 3, 4, 5, 2 ] 环形转线性后得到：[ 3, 4, 5, 2, 3, 4, 5, 2 ] 计算过程： 区间长度2：dp[ 1][ 2] = 3+4 = 7, dp[ 2][ 3 ] = 4+5 = 9, ... 区间长度3：dp[ 1][ 3] = max(dp[ 1][ 2]+dp[ 3][ 3]+sum(1,3), dp[ 1][ 1]+dp[ 2][ 3 ]+sum(1,3)) 最终在dp[ 1][ 4], dp[ 2][ 5], dp[ 3][ 6], dp[ 4][ 7 ]中取最大值 9. 复杂度分析 时间复杂度：O(N³)，需要枚举区间起点、终点和分割点 空间复杂度：O(N²)，用于存储DP表 这种方法通过环形转线性的技巧，将复杂的环形问题转化为标准的区间动态规划问题，是处理环形结构问题的经典思路。