合并石子获得最大得分问题（环形版本）

题目描述
有 N 堆石子排成一个环形，每堆石子的数量用一个数组 stones 表示，其中 stones[i] 表示第 i 堆石子的数量。每次操作可以选择相邻的两堆石子合并为一堆，合并的得分为这两堆石子的数量之和。重复合并操作直到只剩下一堆石子，求所有合并操作的总得分最大值。

解题思路

1. 问题分析：环形结构可以通过将原数组复制一份接在后面，转化为长度为 2N 的线性数组，然后在线性数组上求解长度为 N 的区间内的最大得分。
2. 状态定义：设 dp[i][j] 表示将区间 [i, j] 内的石子合并成一堆所能获得的最大得分。
3. 前缀和优化：预处理前缀和数组 prefix，便于快速计算区间和（即合并代价）。
4. 状态转移：枚举区间分割点 k，将区间 [i, j] 拆分为 [i, k] 和 [k+1, j]，合并得分为两子区间得分之和加上合并代价（即区间 [i, j] 的石子总数）。
5. 环形处理：遍历所有长度为 N 的区间，取最大值作为最终答案。

详细步骤

1. 环形转线性：将原数组 stones 复制一份，得到新数组 arr = stones + stones，长度变为 2N。
2. 前缀和计算：构建前缀和数组 prefix，满足 prefix[i] = arr[0] + arr[1] + ... + arr[i-1]，其中 prefix[0]=0。区间 [i, j] 的和可通过 prefix[j+1] - prefix[i] 快速得到。
3. DP 初始化：对于长度为 1 的区间（即单堆石子），合并得分为 0，因为无需合并。
4. 区间长度递推：
   • 枚举区间长度 len 从 2 到 N（合并至少需要两堆石子）。
   • 枚举区间起点 i，计算终点 j = i + len - 1。
   • 枚举分割点 k ∈ [i, j-1]，更新状态：

     dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + (prefix[j+1] - prefix[i]))
     

5. 环形答案提取：遍历所有起点 i（0 ≤ i < N），计算 dp[i][i+N-1] 的最大值，即为环形合并的最大得分。

示例验证
假设 stones = [3, 4, 5]，N=3：

• 扩展为 arr = [3, 4, 5, 3, 4, 5]。
• 计算前缀和 prefix = [0, 3, 7, 12, 15, 19, 24]。
• 区间 [0, 2] 的得分：枚举 k=0 和 k=1，最终得分为 3+4+5 + max(合并方式) = 12 + max(0+9, 7+5) = 12+12=24。
• 环形最大得分需比较 [0,2]、[1,3]、[2,4] 等区间，最终结果为 24。

关键点

• 环形问题通过复制转化为线性是通用技巧。
• 前缀和优化避免重复计算区间和。
• 状态转移时需遍历所有可能的分割点，确保不漏解。