线性动态规划：石子合并（环形版本）

题目描述
有 \(N\) 堆石子排成一个环形，第 \(i\) 堆石子有 \(a_i\) 的重量（下标从 0 开始）。现在要将这些石子合并成一堆，合并规则是：每次只能合并相邻的两堆石子，合并的代价是这两堆石子的重量之和。合并后的新堆重量为两堆之和，并参与后续合并。目标是求出合并成一堆的最小总代价。

输入：一个数组 \(a\) 表示每堆石子的重量，长度 \(N \geq 1\)。
输出：最小总代价。

示例：
输入：a = [3, 4, 2, 1]
输出：20
解释：一种最优合并顺序（环形展开后的一种线性表示）的代价为 20。

解题过程

1. 问题分析
这是一个经典的区间DP问题，在环形条件下难度升级。

• 线性版本：石子排成一行，用 \(dp[i][j]\) 表示合并第 i 到 j 堆石子的最小代价，转移时枚举最后一次合并的分界点。
• 环形版本：因为首尾相连，合并可以在环上任意位置“断开”成一条链来处理。一种直观思路是：将环形问题转化为长度为 \(2N\) 的线性问题（复制一遍数组），然后对每个长度为 N 的连续子区间求解线性合并问题，取最小值。

2. 状态定义
设 \(n = N\)，复制数组：\(w[0..2n-1]\) 其中 \(w[i] = a[i \bmod n]\)。
定义 \(dp[i][j]\) 表示合并 \(w[i..j]\)（闭区间）这些连续堆（在复制后的数组上）成一堆的最小代价，其中 \(0 \leq i \leq j < 2n\) 且 \(j-i+1 \leq n\)（因为我们只考虑长度不超过 n 的区间，否则就超出环形的一段连续堆了）。
同时，为了快速计算区间和，预处理前缀和数组 \(sum[0..2n]\)，其中 \(sum[k] = \sum_{t=0}^{k-1} w[t]\)，则区间 [i, j] 的石子总重量为 \(sum[j+1] - sum[i]\)。

3. 状态转移方程
对于区间 [i, j]：

• 如果 i == j，则只有一堆，不需要合并，代价为 0。
• 否则，我们枚举最后一次合并的位置 k（i ≤ k < j），表示先合并 [i, k] 和 [k+1, j] 两堆，再将这两堆合并。
  合并 [i, j] 的最小代价 = 合并 [i, k] 的最小代价 + 合并 [k+1, j] 的最小代价 + 区间 [i, j] 的石子总重量。
  即：

\[ dp[i][j] = \min_{k = i}^{j-1} (dp[i][k] + dp[k+1][j]) + (sum[j+1] - sum[i]) \]

其中 \(dp[i][i] = 0\)。

4. 环形处理
我们只需要计算所有长度为 n 的区间 [i, i+n-1] 的合并最小代价，然后取最小值：

\[\min_{i=0}^{n-1} dp[i][i+n-1] \]

这就是环形合并为 1 堆的最小代价。

5. 计算顺序
因为区间长度从 1 到 n 逐步增大，所以我们按区间长度 len 从小到大计算。
对于每个长度 len，枚举起点 i，然后终点 j = i + len - 1，再枚举分界点 k。
注意：i 的范围是 0 到 2n-len-1，确保 j 不越界。

6. 示例推演
输入 a = [3, 4, 2, 1]，n=4。
复制数组 w = [3,4,2,1,3,4,2,1]。
计算前缀和 sum = [0,3,7,9,10,13,17,19,20]。

我们只需计算长度 len = 4 的区间 [i, i+3] 的 dp 值（最终合并成一堆的代价）。

• 当 i=0，区间 [0,3]（对应原环形顺序 3,4,2,1）：
  先计算长度较小的区间：
  len=1: dp[x][x]=0。
  len=2: dp[0][1]=0+0+(7-0)=7，dp[1][2]=0+0+(9-3)=6，dp[2][3]=0+0+(10-7)=3，dp[3][4]=0+0+(13-10)=3，等等（只列一部分）。
  len=3: dp[0][2] = min( dp[0][0]+dp[1][2], dp[0][1]+dp[2][2] ) + (9-0) = min(0+6, 7+0)+9 = min(6,7)+9=15。
  dp[1][3] = min( dp[1][1]+dp[2][3], dp[1][2]+dp[3][3] ) + (10-3) = min(0+3, 6+0)+7 = 3+7=10。
  len=4: dp[0][3] = min( k=0: dp[0][0]+dp[1][3], k=1: dp[0][1]+dp[2][3], k=2: dp[0][2]+dp[3][3] ) + (10-0)
  = min(0+10, 7+3, 15+0) + 10 = min(10, 10, 15) + 10 = 10 + 10 = 20。

• 同理计算 i=1 区间 [1,4]（对应 4,2,1,3）：最后得到 20。
  i=2 区间 [2,5]（对应 2,1,3,4）：20。
  i=3 区间 [3,6]（对应 1,3,4,2）：20。
  所以最小代价为 20。

7. 时间复杂度与空间优化

• 朴素实现：状态数 O((2n)^2) = O(n^2)，每个状态枚举 k 为 O(n)，总 O(n^3)。
• 可以用四边形不等式优化到 O(n^2)，但这里不展开。
• 空间复杂度 O(n^2)。

8. 实现框架（伪代码）

def mergeStones_ring(a):
    n = len(a)
    w = a + a
    m = 2 * n
    prefix = [0] * (m + 1)
    for i in range(m):
        prefix[i+1] = prefix[i] + w[i]
    dp = [[0] * m for _ in range(m)]
    for length in range(2, n+1):  # 区间长度
        for i in range(m - length + 1):
            j = i + length - 1
            dp[i][j] = float('inf')
            for k in range(i, j):
                cost = dp[i][k] + dp[k+1][j] + (prefix[j+1] - prefix[i])
                if cost < dp[i][j]:
                    dp[i][j] = cost
    ans = min(dp[i][i+n-1] for i in range(n))
    return ans

9. 思考扩展

• 如果要求合并成一堆的最大代价，只需将 min 改为 max。
• 如果环形石子合并要求合并成 k 堆（k>1）的最小代价，则需要增加一维状态表示堆数，变成三维 DP（类似“石子合并”的一般问题）。
• 如果石子堆数很大（n 上千），需要用四边形不等式优化到 O(n^2) 或贪心算法（Huffman 树只适用于任意两堆合并，本题是相邻合并，不适用）。

这个环形石子合并问题是区间 DP 的经典例题，掌握了它可以处理很多类似环形区间合并问题。