环形石子合并（环形数组最小得分版本）

题目描述

有一个环形数组 stones，长度为 n。数组中的每个元素 stones[i] 表示第 i 堆石子的数量。
游戏规则如下：

1. 每次只能合并相邻的两堆石子，合并的成本是这两堆石子的数量之和。
2. 合并后，新的一堆石子的数量是原来两堆之和，并占据原来两堆的位置（即数组长度减 1）。
3. 重复合并，直到只剩下一堆石子。

问：将所有石子合并成一堆的最小总成本是多少？

注意：由于是环形，第一堆和最后一堆也被视为相邻。
换句话说，我们可以从环形的任意位置断开，展开成一个线性数组，然后按照线性石子合并的规则进行合并，最后取最小成本。

示例：
输入：stones = [3, 4, 2, 5]
输出：28
解释：
一种最优合并顺序（从索引 0 开始断开，得到线性数组 [3, 4, 2, 5]）：

• 合并 3 和 4，成本 7，数组变为 [7, 2, 5]
• 合并 2 和 5，成本 7，数组变为 [7, 7]
• 合并 7 和 7，成本 14，数组变为 [14]
  总成本 = 7 + 7 + 14 = 28。

解题思路

这个问题是“线性石子合并”的环形版本。
如果我们把它展开成线性数组，长度是 n，但合并时需要考虑所有可能的起点。
一个常见技巧是：将原数组复制一份接在后面，形成一个长度为 2n 的数组，然后在这个数组上做线性石子合并，但只合并长度为 n 的区间。
通过动态规划计算所有可能起点、所有长度的合并最小成本，最后取最小值。

详细步骤

1. 将环形转为线性

设原数组为 stones[0..n-1]。
构造一个新数组 a，长度为 2n，其中：

a[i] = stones[i % n]  (i = 0..2n-1)

例如 stones = [3,4,2,5]，则 a = [3,4,2,5,3,4,2,5]。

为什么这样做？
如果我们从环形数组的第 i 堆开始作为线性数组的第一个元素，那么对应的线性数组就是 a[i..i+n-1]。
我们可以在 a 上对任意长度为 n 的区间做线性石子合并，其最小成本就是从这个起点开始合并的最小成本。
最后取所有起点中的最小值。

2. 前缀和

为了快速求任意区间 [i, j] 的石子总数（合并成本时需要），我们先计算 a 的前缀和 prefix：

prefix[0] = 0
prefix[k] = a[0] + a[1] + ... + a[k-1]  (k = 1..2n)

这样区间 [i, j] 的和 = prefix[j+1] - prefix[i]，时间复杂度 O(1)。

3. 动态规划定义

设 dp[i][j] 表示在数组 a 上，合并区间 [i, j] 内的所有石子成一堆的最小成本。
其中 i <= j，并且区间长度 len = j - i + 1 不超过 n（因为我们只关心长度 ≤ n 的区间）。
dp[i][j] 的计算方式与线性石子合并相同。

转移方程：
考虑最后一次合并是将 [i, k] 和 [k+1, j] 两堆合并成一堆。
那么合并成本是 dp[i][k] + dp[k+1][j] + sum(i, j)，其中 sum(i, j) 是区间 [i, j] 的石子总数（用前缀和计算）。
我们枚举分界点 k，取最小值：

dp[i][j] = min{ dp[i][k] + dp[k+1][j] + sum(i,j) }  (k = i..j-1)

初始条件：dp[i][i] = 0（只有一堆，不需要合并，成本 0）。

4. 区间DP的遍历顺序

由于 dp[i][j] 依赖于长度更短的区间，我们按区间长度 len 从小到大计算：

• len = 1 时，dp[i][i] = 0
• len = 2, 3, ..., n 时，依次计算。

注意：我们只需要计算 len ≤ n 的区间，并且 i 的取值范围是 0..2n-1，但要保证 j = i+len-1 < 2n。

5. 计算最终答案

对于原问题的环形数组，我们考虑所有可能的起点 i（0 ≤ i < n），对应的区间是 [i, i+n-1]。
这个区间合并成一堆的最小成本是 dp[i][i+n-1]。
答案是所有起点的最小值：

ans = min{ dp[i][i+n-1] }  (i = 0..n-1)

6. 举例说明

以 stones = [3, 4, 2, 5] 为例。

构造 a = [3,4,2,5,3,4,2,5]，n=4。

前缀和（略）。

计算 dp（只展示关键结果）：

• 当起点 i=0，区间 [0,3] 就是原数组 [3,4,2,5]。
  线性石子合并的最小成本是 28（前面示例已算过）。
• 当起点 i=1，区间 [1,4] 是 [4,2,5,3]，计算它的最小合并成本。
• 当起点 i=2，区间 [2,5] 是 [2,5,3,4]。
• 当起点 i=3，区间 [3,6] 是 [5,3,4,2]。

计算这些区间的最小成本，取最小值，得到 28。

7. 时间复杂度

• 状态数：O(n²)（因为区间长度 ≤ n，起点 ≤ 2n，但区间总数约为 2n×n/2 = O(n²)）
• 每个状态枚举分界点 k：O(n)
• 总时间复杂度 O(n³)
• 空间复杂度 O(n²)

对于 n ≤ 250 的典型题目规模，O(n³) 可行。
但注意如果 n 较大（如 1000），需要优化（如四边形不等式优化到 O(n²)）。

代码框架（Python风格伪代码）

def minCost(stones):
    n = len(stones)
    a = stones + stones  # 长度 2n
    prefix = [0] * (2*n + 1)
    for i in range(1, 2*n + 1):
        prefix[i] = prefix[i-1] + a[i-1]
    
    def sum_range(l, r):
        return prefix[r+1] - prefix[l]
    
    dp = [[0] * (2*n) for _ in range(2*n)]
    for length in range(2, n+1):  # 区间长度
        for i in range(2*n - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + sum_range(i, j))
    
    ans = float('inf')
    for i in range(n):
        ans = min(ans, dp[i][i+n-1])
    return ans

关键点总结

1. 环形转线性的方法：复制数组接在后面，枚举起点。
2. 区间DP的状态表示：合并某区间的最小成本。
3. 转移时枚举最后一次合并的分界点。
4. 最终答案在所有可能的起点中取最小。

这样，我们就用区间动态规划解决了“环形石子合并”的最小成本问题。