环形石子合并（最小得分）问题
字数 2472 2025-12-05 17:34:36

环形石子合并（最小得分）问题

我们先看题目描述：
有 n 堆石子排成一个环形，第 i 堆石子有重量 stones[i]（stones 下标从 0 开始）。每次可以合并相邻的两堆石子，合并的代价是这两堆石子的重量之和，合并后的新堆重量也是这两堆石子重量之和。不断合并直到只剩下一堆石子，求最小的总代价。

1. 问题分析

线性版本（石子排成一行）是经典的区间 DP 问题，状态定义为：

dp[l][r] = 合并区间 [l, r] 内的所有石子成一堆的最小代价。

转移方程：
dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum[l][r])，其中 sum[l][r] 是区间石子重量和，k 是分界点。

现在石子是环形，也就是 stones[n] 后面接着 stones[0]。
一种常见处理方式：将原数组复制一份接到后面，长度变成 2n，然后在这个长度为 2n 的数组上做线性区间 DP，但只考虑长度 n 的区间，然后枚举起点，取最小值。

为什么这样可行？
环形时，长度为 n 的区间对应原环上连续的一段，通过枚举起点，就覆盖了所有可能的合并顺序在环上的情况。

2. 状态定义与初始化

设 n 是原始石子堆数，构造数组 a[0..2n-1]，其中
a[i] = stones[i % n]，i = 0..2n-1。

定义 dp[l][r] 为将 a[l..r] 合并成一堆的最小代价（l ≤ r）。

初始化：
dp[i][i] = 0，因为只有一堆时不需要合并，代价 0。

前缀和数组 prefix 用于快速计算区间和：
prefix[0] = 0，prefix[i+1] = prefix[i] + a[i]，则
sum[l][r] = prefix[r+1] - prefix[l]。

3. 状态转移方程

我们按区间长度 len 从小到大计算，len 从 2 到 n（因为环上合并时，我们最终考虑的长度最大为 n）。

对于每个区间 [l, r]（r = l + len - 1），枚举分界点 k 从 l 到 r-1：

\[dp[l][r] = \min_{k=l}^{r-1} \big( dp[l][k] + dp[k+1][r] + (prefix[r+1] - prefix[l]) \big) \]

区间和 sum[l][r] 是合并最后两堆时的代价，在递归思想里，合并 [l,k] 和 [k+1,r] 时，总重量就是 sum[l][r]，所以要加上。

4. 环形处理与答案计算

在 2n 的数组上计算完所有长度从 1 到 n 的区间最小代价后，
答案 = \(\min_{i=0}^{n-1} dp[i][i+n-1]\)。

解释：dp[i][i+n-1] 对应原环上从 i 开始连续 n 堆合并的代价，枚举所有起点 i 得到全局最小。

5. 示例推演

例：stones = [1, 2, 3]，n=3。

构造 a = [1, 2, 3, 1, 2, 3]。

前缀和 prefix = [0, 1, 3, 6, 7, 9, 12]。

计算部分过程（只给出关键值，方便理解）：

长度 len=2：
dp[0][1] = dp[0][0]+dp[1][1]+sum=0+0+3=3
dp[1][2] = 0+0+5=5
dp[2][3] = 0+0+4=4
等等。

长度 len=3（最终我们关心的长度 n=3）：
计算 dp[0][2]：
k=0: dp[0][0]+dp[1][2]+sum[0..2]=0+5+6=11
k=1: dp[0][1]+dp[2][2]+6=3+0+6=9
取 min=9。
这是线性数组 [1,2,3] 合并最小代价（与环形无关）。

为得到环形最小，看 dp[0][2]、dp[1][3]、dp[2][4]：

  • dp[0][2] = 9（合并 [1,2,3]）

  • dp[1][3] 对应数组 [2,3,1]：
    先合并 2+3=5 得 (5,1)，再合并 5+1=6，总 5+6=11？我们按 DP 算：
    sum[1..3]=6
    k=1: dp[1][1]+dp[2][3]+6=0+4+6=10
    k=2: dp[1][2]+dp[3][3]+6=5+0+6=11
    取 10。
    其实手工：合并 2+3=5，合并 5+1=6，总 5+6=11 是错的？注意第一次合并 2,3 得 5 代价 5，剩下 (5,1)，合并 5+1=6 代价 6，总 11。但 DP 得 10，说明有更优法：先合并 3+1=4 代价 4，剩下 (2,4) 合并代价 6，总 4+6=10。对，环形中 [2,3,1] 最小 10。

  • dp[2][4] 对应数组 [3,1,2]：
    sum=6
    k=2: 0+dp[3][4](1+2=3)+6=0+3+6=9
    k=3: dp[2][3](4)+0+6=10
    取 9。

最终答案 = min(9, 10, 9) = 9。

检验：环形 1,2,3
合并 1+2=3 代价 3，得 (3,3) 合并代价 6，总 9。正确。

6. 算法总结

  1. 将原数组复制一次接在后面，得到长度 2n 的数组。
  2. 计算前缀和以便 O(1) 得到区间和。
  3. 区间 DP 计算所有 dp[l][r]（1 ≤ len ≤ n）。
  4. 答案 = 对所有起点 i 取 dp[i][i+n-1] 的最小值。
  5. 时间复杂度 O(n³)，空间 O(n²)。

这样我们就解决了环形石子合并（最小得分）问题。这种方法的核心是“破环成链”，把环形问题转化为线性区间 DP 的枚举。

环形石子合并（最小得分）问题 我们先看题目描述： 有 n 堆石子排成一个环形，第 i 堆石子有重量 stones[i] （ stones 下标从 0 开始）。每次可以合并 相邻 的两堆石子，合并的代价是这两堆石子的重量之和，合并后的新堆重量也是这两堆石子重量之和。不断合并直到只剩下一堆石子，求 最小的总代价 。 1. 问题分析 线性版本（石子排成一行）是经典的区间 DP 问题，状态定义为： dp[l][r] = 合并区间 [l, r] 内的所有石子成一堆的 最小代价 。 转移方程： dp[l][r] = min(dp[l][k] + dp[k+1][r] + sum[l][r]) ，其中 sum[l][r] 是区间石子重量和， k 是分界点。 现在石子是 环形 ，也就是 stones[n] 后面接着 stones[0] 。 一种常见处理方式：将原数组复制一份接到后面，长度变成 2n ，然后在这个长度为 2n 的数组上做线性区间 DP，但只考虑长度 n 的区间，然后枚举起点，取最小值。 为什么这样可行 ？ 环形时，长度为 n 的区间对应原环上连续的一段，通过枚举起点，就覆盖了所有可能的合并顺序在环上的情况。 2. 状态定义与初始化 设 n 是原始石子堆数，构造数组 a[0..2n-1] ，其中 a[i] = stones[i % n] ， i = 0..2n-1 。 定义 dp[l][r] 为将 a[l..r] 合并成一堆的最小代价（ l ≤ r ）。 初始化： dp[i][i] = 0 ，因为只有一堆时不需要合并，代价 0。 前缀和数组 prefix 用于快速计算区间和： prefix[0] = 0 ， prefix[i+1] = prefix[i] + a[i] ，则 sum[l][r] = prefix[r+1] - prefix[l] 。 3. 状态转移方程 我们按区间长度 len 从小到大计算， len 从 2 到 n （因为环上合并时，我们最终考虑的长度最大为 n ）。 对于每个区间 [l, r] （ r = l + len - 1 ），枚举分界点 k 从 l 到 r-1 ： \[ dp[ l][ r] = \min_ {k=l}^{r-1} \big( dp[ l][ k] + dp[ k+1][ r] + (prefix[ r+1] - prefix[ l ]) \big) \] 区间和 sum[l][r] 是合并最后两堆时的代价，在递归思想里，合并 [l,k] 和 [k+1,r] 时，总重量就是 sum[l][r] ，所以要加上。 4. 环形处理与答案计算 在 2n 的数组上计算完所有长度从 1 到 n 的区间最小代价后， 答案 = \(\min_ {i=0}^{n-1} dp[ i][ i+n-1 ]\)。 解释 ： dp[i][i+n-1] 对应原环上从 i 开始连续 n 堆合并的代价，枚举所有起点 i 得到全局最小。 5. 示例推演 例： stones = [1, 2, 3] ，n=3。 构造 a = [1, 2, 3, 1, 2, 3] 。 前缀和 prefix = [ 0, 1, 3, 6, 7, 9, 12 ]。 计算部分过程 （只给出关键值，方便理解）： 长度 len=2： dp[0][1] = dp[0][0]+dp[1][1]+sum=0+0+3=3 dp[1][2] = 0+0+5=5 dp[2][3] = 0+0+4=4 等等。 长度 len=3（最终我们关心的长度 n=3）： 计算 dp[0][2] ： k=0: dp[0][0]+dp[1][2]+sum[0..2]=0+5+6=11 k=1: dp[0][1]+dp[2][2]+6=3+0+6=9 取 min=9。 这是线性数组 [ 1,2,3 ] 合并最小代价（与环形无关）。 为得到环形最小，看 dp[0][2] 、 dp[1][3] 、 dp[2][4] ： dp[0][2] = 9（合并 [ 1,2,3 ]） dp[1][3] 对应数组 [ 2,3,1 ]： 先合并 2+3=5 得 (5,1)，再合并 5+1=6，总 5+6=11？我们按 DP 算： sum[ 1..3 ]=6 k=1: dp[1][1]+dp[2][3]+6=0+4+6=10 k=2: dp[1][2]+dp[3][3]+6=5+0+6=11 取 10。 其实手工：合并 2+3=5，合并 5+1=6，总 5+6=11 是错的？注意第一次合并 2,3 得 5 代价 5，剩下 (5,1)，合并 5+1=6 代价 6，总 11。但 DP 得 10，说明有更优法：先合并 3+1=4 代价 4，剩下 (2,4) 合并代价 6，总 4+6=10。对，环形中 [ 2,3,1 ] 最小 10。 dp[2][4] 对应数组 [ 3,1,2 ]： sum=6 k=2: 0+ dp[3][4] (1+2=3)+6=0+3+6=9 k=3: dp[2][3] (4)+0+6=10 取 9。 最终答案 = min(9, 10, 9) = 9。 检验：环形 1,2,3 合并 1+2=3 代价 3，得 (3,3) 合并代价 6，总 9。正确。 6. 算法总结 将原数组复制一次接在后面，得到长度 2n 的数组。 计算前缀和以便 O(1) 得到区间和。 区间 DP 计算所有 dp[l][r] （ 1 ≤ len ≤ n ）。 答案 = 对所有起点 i 取 dp[i][i+n-1] 的最小值。 时间复杂度 O(n³)，空间 O(n²)。 这样我们就解决了环形石子合并（最小得分）问题。这种方法的核心是“破环成链”，把环形问题转化为线性区间 DP 的枚举。