石子合并问题（环形数组版本）

题目描述
有 n 堆石子排成一个环形，每堆石子的数量用一个数组 stones 表示（环形意味着 stones[0] 和 stones[n-1] 相邻）。每次操作可以选择相邻的两堆石子合并成一堆，合并的代价为这两堆石子的数量之和。重复合并操作直到只剩下一堆石子，求合并的最小总代价。

示例
输入：stones = [3, 4, 2, 5]（环形排列）
输出：最小总代价为 31
解释：一种最优合并顺序为：

1. 合并 2 和 5（代价 7），剩余 [3, 4, 7]
2. 合并 3 和 4（代价 7），剩余 [7, 7]
3. 合并 7 和 7（代价 14），总代价 7 + 7 + 14 = 28（但注意环形下最优解可能不同，需动态规划计算）。

解题步骤

1. 问题转换

   • 环形问题不易直接处理，可将其转化为线性问题：将原数组复制一份接在原数组末尾，形成长度为 2n 的数组 arr。
   • 例如 stones = [3, 4, 2, 5] 转换为 arr = [3, 4, 2, 5, 3, 4, 2, 5]。
   • 在 arr 中任意长度为 n 的连续子数组都对应环形的一种起点情况。通过计算所有起点情况的最小代价，取最小值即为环形问题的解。

2. 定义状态

   • 设 dp[i][j] 表示合并 arr 中第 i 到第 j 堆石子的最小代价（i 和 j 为索引，从 0 开始）。
   • 目标：求所有长度为 n 的区间 [i, i+n-1] 中 dp[i][i+n-1] 的最小值。

3. 前缀和预处理

   • 为了快速计算区间和，预处理前缀和数组 prefix：
     prefix[k] = arr[0] + arr[1] + ... + arr[k]（k 从 0 开始）。
   • 区间 [i, j] 的石子总和为 prefix[j] - prefix[i-1]（当 i=0 时需特殊处理）。

4. 状态转移方程

   • 将区间 [i, j] 拆分为两个子区间 [i, k] 和 [k+1, j]（i ≤ k < j）。
   • 合并 [i, j] 的代价 = 合并 [i, k] 的代价 + 合并 [k+1, j] 的代价 + 区间 [i, j] 的石子总和。
   • 状态转移方程：

     dp[i][j] = min(dp[i][k] + dp[k+1][j]) + (prefix[j] - prefix[i-1])
     其中 k 遍历 [i, j-1]
     

5. 初始化与计算顺序

   • 初始化：单个石堆无需合并，代价为 0，即 dp[i][i] = 0。
   • 计算顺序：按区间长度 len 从小到大的顺序计算（len 从 2 到 n）。
   • 注意：在复制后的数组 arr 上，只需计算长度不超过 n 的区间。

6. 环形情况处理

   • 遍历所有起点 i（0 ≤ i < n），计算 dp[i][i+n-1] 的最小值。

完整示例计算（以 stones = [3, 4, 2, 5] 为例）

1. 构造 arr = [3, 4, 2, 5, 3, 4, 2, 5]，n = 4。
2. 前缀和 prefix = [3, 7, 9, 14, 17, 21, 23, 28]。
3. 计算所有区间长度从 2 到 4 的 dp[i][j]：
   • 长度 2：dp[0][1] = 0+0+(7-0)=7，类似计算其他区间。
   • 长度 3 和 4 时枚举所有分割点，取最小值。
4. 对起点 i=0,1,2,3 计算 dp[i][i+3]，取最小值得到最终结果 31。

关键点

• 环形转线性通过复制数组实现，避免复杂边界处理。
• 区间 DP 需按长度递增顺序计算，确保子问题先被解决。
• 时间复杂度 O(n³)，空间复杂度 O(n²)。