石子合并（环形数组最小得分）问题
字数 2810 2025-12-06 12:01:24

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

题目描述
有 n 堆石子排成一个环形，第 i 堆石子有 weights[i] 的重量。现在需要将这些石子合并成一堆，合并规则是：每次只能合并相邻的两堆石子，合并的代价是这两堆石子的重量之和。合并后的新堆石子的重量是原来两堆石子重量之和。不断重复这个过程直到只剩下一堆石子。请求出将环形石子全部合并成一堆的最小总代价。

示例
输入：weights = [4, 4, 5, 9]
输出：43
解释：
环形排列为 4, 4, 5, 9。
一种最优合并顺序：

  1. 合并前两堆 (4, 4)，代价 8，得到 [8, 5, 9]
  2. 合并前两堆 (8, 5)，代价 13，得到 [13, 9]
  3. 合并最后两堆 (13, 9)，代价 22，得到一堆
    总代价 = 8 + 13 + 22 = 43

解题过程

1. 问题分析
本题是经典石子合并问题的“环形”版本。

  • 如果是线性排列，我们可以用区间 DP 解决。
  • 环形意味着第 1 堆和第 n 堆也是相邻的，这增加了合并顺序的多样性。
  • 一个技巧：将原数组复制一份接在后面，变成长度为 2n 的数组，在这个数组上对任意长度为 n 的连续子序列做线性石子合并的最小代价，然后取所有可能起点对应的最小值。

2. 状态定义
设 dp[i][j] 表示在“扩展后的线性数组”中，合并第 i 堆到第 j 堆（闭区间）的所有石子成一堆的最小总代价。

  • 这里 i 和 j 对应扩展数组的下标，范围为 0 到 2n-1，但实际合并区间长度不能超过 n（因为环形最多 n 堆石子）。
  • 但为了 DP 方便，我们先不限制 i 和 j 的范围长度，在计算时注意区间长度不超过 n 即可。

3. 状态转移
考虑最后一次合并：在合并区间 [i, j] 时，最后一步一定是将 [i, k] 和 [k+1, j] 两堆合并（i ≤ k < j）。
合并代价是 dp[i][k] + dp[k+1][j] + sum(i, j)，其中 sum(i, j) 是区间内石子总重量。
所以状态转移方程为：

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

初始条件：dp[i][i] = 0，因为单独一堆不需要合并代价。

4. 前缀和优化
为了快速计算 sum(i, j)，我们预处理前缀和数组 prefix，使得 prefix[0] = 0，prefix[t] = weights[0] + ... + weights[t-1]（在扩展数组上做）。
那么：

\[\text{sum}(i, j) = \text{prefix}[j+1] - \text{prefix}[i] \]

注意扩展数组的长度是 2n，weights 重复一遍。

5. 环形处理
扩展数组为 ext = weights + weights（长度为 2n）。
在扩展数组上，对每个可能的起点 start（0 ≤ start < n），计算合并区间 [start, start + n - 1] 的最小代价，即 dp[start][start + n - 1]。
最终答案就是所有可能的 start 对应的最小值。

6. DP 计算顺序
区间 DP 通常按区间长度从小到大计算。

  • 长度 len 从 2 到 n（因为最终要合并长度为 n 的区间）。
  • 对每个 len，枚举起点 i，计算 j = i + len - 1。
  • 在扩展数组上，j 最大为 2n-1，但 i 最大为 2n - len。
  • 计算 dp[i][j] 时，枚举分割点 k 从 i 到 j-1。

7. 举例说明
输入 weights = [4, 4, 5, 9]，n=4。
扩展数组：ext = [4, 4, 5, 9, 4, 4, 5, 9]。
前缀和 prefix：[0, 4, 8, 13, 22, 26, 30, 35, 44]。
我们需要计算 len=4 的情况，即区间长度 4 的合并最小代价。

计算 dp[0][3]（对应原数组位置 0~3 的线性合并）：
len=2:

  • dp[0][1] = 0+0+(4+4)=8
  • dp[1][2] = 0+0+(4+5)=9
  • dp[2][3] = 0+0+(5+9)=14
    len=3:
  • dp[0][2] = min( dp[0][0]+dp[1][2]+sum(0,2), dp[0][1]+dp[2][2]+sum(0,2) )
    = min(0+9+13, 8+0+13) = min(22, 21) = 21
  • dp[1][3] = min( dp[1][1]+dp[2][3]+sum(1,3), dp[1][2]+dp[3][3]+sum(1,3) )
    = min(0+14+18, 9+0+18) = min(32, 27) = 27
    len=4:
    dp[0][3] = min(
  • dp[0][0]+dp[1][3]+sum(0,3) = 0+27+22=49
  • dp[0][1]+dp[2][3]+sum(0,3) = 8+14+22=44
  • dp[0][2]+dp[3][3]+sum(0,3) = 21+0+22=43
    ) = 43

所以从起点 0 开始的环形合并最小代价是 43。
我们还要检查起点 1,2,3 的情况，但因为是对称的，最小值就是 43。

8. 时间复杂度
状态数 O(n²)（在扩展数组上最多 2n 长度，但只用到长度 n 区间），每个状态枚举分割点 O(n)，总 O(n³)。
可以用四边形不等式优化到 O(n²)，但这里不展开。

9. 总结步骤

  1. 将原数组复制一份接在后面，形成扩展数组 ext[0..2n-1]。
  2. 计算扩展数组的前缀和 prefix。
  3. 初始化 dp 为 0（dp[i][i]=0）。
  4. 按区间长度 len 从 2 到 n 遍历：
    • 遍历起点 i 从 0 到 2n-len：
      • j = i + len - 1
      • dp[i][j] = ∞
      • 遍历分割点 k 从 i 到 j-1：
        dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + prefix[j+1]-prefix[i])
  5. 最终答案 = min(dp[start][start+n-1])，其中 start=0..n-1。

这样就能求出环形石子合并的最小总代价。

石子合并（环形数组最小得分）问题 题目描述 有 n 堆石子排成一个环形，第 i 堆石子有 weights[i] 的重量。现在需要将这些石子合并成一堆，合并规则是：每次只能合并相邻的两堆石子，合并的代价是这两堆石子的重量之和。合并后的新堆石子的重量是原来两堆石子重量之和。不断重复这个过程直到只剩下一堆石子。请求出将环形石子全部合并成一堆的最小总代价。 示例 输入： weights = [4, 4, 5, 9] 输出： 43 解释： 环形排列为 4, 4, 5, 9。 一种最优合并顺序： 合并前两堆 (4, 4)，代价 8，得到 [ 8, 5, 9 ] 合并前两堆 (8, 5)，代价 13，得到 [ 13, 9 ] 合并最后两堆 (13, 9)，代价 22，得到一堆 总代价 = 8 + 13 + 22 = 43 解题过程 1. 问题分析 本题是经典石子合并问题的“环形”版本。 如果是线性排列，我们可以用区间 DP 解决。 环形意味着第 1 堆和第 n 堆也是相邻的，这增加了合并顺序的多样性。 一个技巧：将原数组复制一份接在后面，变成长度为 2n 的数组，在这个数组上对任意长度为 n 的连续子序列做线性石子合并的最小代价，然后取所有可能起点对应的最小值。 2. 状态定义 设 dp[i][j] 表示在“扩展后的线性数组”中，合并第 i 堆到第 j 堆（闭区间）的所有石子成一堆的最小总代价。 这里 i 和 j 对应扩展数组的下标，范围为 0 到 2n-1，但实际合并区间长度不能超过 n（因为环形最多 n 堆石子）。 但为了 DP 方便，我们先不限制 i 和 j 的范围长度，在计算时注意区间长度不超过 n 即可。 3. 状态转移 考虑最后一次合并：在合并区间 [i, j] 时，最后一步一定是将 [i, k] 和 [k+1, j] 两堆合并（i ≤ k < j）。 合并代价是 dp[i][k] + dp[k+1][j] + sum(i, j) ，其中 sum(i, j) 是区间内石子总重量。 所以状态转移方程为： \[ dp[ i][ j] = \min_ {k=i}^{j-1} \{ dp[ i][ k] + dp[ k+1][ j ] + \text{sum}(i, j) \} \] 初始条件： dp[i][i] = 0 ，因为单独一堆不需要合并代价。 4. 前缀和优化 为了快速计算 sum(i, j) ，我们预处理前缀和数组 prefix ，使得 prefix[0] = 0 ， prefix[t] = weights[0] + ... + weights[t-1] （在扩展数组上做）。 那么： \[ \text{sum}(i, j) = \text{prefix}[ j+1] - \text{prefix}[ i ] \] 注意扩展数组的长度是 2n， weights 重复一遍。 5. 环形处理 扩展数组为 ext = weights + weights （长度为 2n）。 在扩展数组上，对每个可能的起点 start （0 ≤ start < n），计算合并区间 [start, start + n - 1] 的最小代价，即 dp[start][start + n - 1] 。 最终答案就是所有可能的 start 对应的最小值。 6. DP 计算顺序 区间 DP 通常按区间长度从小到大计算。 长度 len 从 2 到 n（因为最终要合并长度为 n 的区间）。 对每个 len，枚举起点 i，计算 j = i + len - 1。 在扩展数组上，j 最大为 2n-1，但 i 最大为 2n - len。 计算 dp[i][j] 时，枚举分割点 k 从 i 到 j-1。 7. 举例说明 输入 weights = [4, 4, 5, 9] ，n=4。 扩展数组： ext = [4, 4, 5, 9, 4, 4, 5, 9] 。 前缀和 prefix ： [0, 4, 8, 13, 22, 26, 30, 35, 44] 。 我们需要计算 len=4 的情况，即区间长度 4 的合并最小代价。 计算 dp[0][3] （对应原数组位置 0~3 的线性合并）： len=2: dp[ 0][ 1 ] = 0+0+(4+4)=8 dp[ 1][ 2 ] = 0+0+(4+5)=9 dp[ 2][ 3 ] = 0+0+(5+9)=14 len=3: dp[ 0][ 2] = min( dp[ 0][ 0]+dp[ 1][ 2]+sum(0,2), dp[ 0][ 1]+dp[ 2][ 2 ]+sum(0,2) ) = min(0+9+13, 8+0+13) = min(22, 21) = 21 dp[ 1][ 3] = min( dp[ 1][ 1]+dp[ 2][ 3]+sum(1,3), dp[ 1][ 2]+dp[ 3][ 3 ]+sum(1,3) ) = min(0+14+18, 9+0+18) = min(32, 27) = 27 len=4: dp[ 0][ 3 ] = min( dp[ 0][ 0]+dp[ 1][ 3 ]+sum(0,3) = 0+27+22=49 dp[ 0][ 1]+dp[ 2][ 3 ]+sum(0,3) = 8+14+22=44 dp[ 0][ 2]+dp[ 3][ 3 ]+sum(0,3) = 21+0+22=43 ) = 43 所以从起点 0 开始的环形合并最小代价是 43。 我们还要检查起点 1,2,3 的情况，但因为是对称的，最小值就是 43。 8. 时间复杂度 状态数 O(n²)（在扩展数组上最多 2n 长度，但只用到长度 n 区间），每个状态枚举分割点 O(n)，总 O(n³)。 可以用四边形不等式优化到 O(n²)，但这里不展开。 9. 总结步骤 将原数组复制一份接在后面，形成扩展数组 ext[ 0..2n-1 ]。 计算扩展数组的前缀和 prefix。 初始化 dp 为 0（dp[ i][ i ]=0）。 按区间长度 len 从 2 到 n 遍历： 遍历起点 i 从 0 到 2n-len： j = i + len - 1 dp[ i][ j ] = ∞ 遍历分割点 k 从 i 到 j-1： dp[ i][ j] = min(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j] + prefix[ j+1]-prefix[ i ]) 最终答案 = min(dp[ start][ start+n-1 ])，其中 start=0..n-1。 这样就能求出环形石子合并的最小总代价。