环形石子合并的最大得分问题

字数 1640 2025-10-29 11:31:55

环形石子合并的最大得分问题

题目描述
有 n 堆石子排成一个环形，每堆石子的数量用一个数组 stones 表示，其中 stones[i] 表示第 i 堆石子的数量。每次操作可以选择相邻的两堆石子合并为一堆，合并的得分为这两堆石子的数量之和。合并后新堆的石子数为两堆之和，新堆与左右两边的石子堆相邻。重复操作直到只剩下一堆石子。求所有合并操作能获得的最大总得分。

示例
输入：stones = [3, 4, 5, 6]（环形排列）
解释：环形意味着 stones[0] 和 stones[3] 也相邻。

解题思路

环形处理技巧
将环形数组复制一份接在原数组末尾，形成长度为 2n 的线性数组。例如，[3,4,5,6] 扩展为 [3,4,5,6,3,4,5,6]。这样，原环形的任意连续区间都对应新线性数组中长度为 n 以内的某个区间。
状态定义
设 dp[i][j] 表示合并线性数组中第 i 到第 j 堆石子（闭区间）所能获得的最大得分。注意：合并后剩余一堆石子，但过程中需要记录区间和，因此需预处理前缀和数组 prefix，以便快速计算区间和。
状态转移方程
- 若区间长度 len = 1（即 i = j），只有一堆石子，无需合并，得分 dp[i][j] = 0。
- 若区间长度 len ≥ 2，枚举最后一次合并的分割点 k（i ≤ k < j），将区间分为 [i, k] 和 [k+1, j]。合并这两部分的得分为区间 [i, j] 的石子总数，即 prefix[j+1] - prefix[i]。
  转移方程：
```
dp[i][j] = max(dp[i][k] + dp[k+1][j] + (prefix[j+1] - prefix[i]))
```
  需遍历所有 k 取最大值。
环形答案提取
环形问题的最终答案为所有长度为 n 的区间对应的 dp[i][i+n-1] 中的最大值。

详细步骤（以示例为例）

输入 stones = [3, 4, 5, 6]，n = 4。
扩展为线性数组：[3,4,5,6,3,4,5,6]，长度 2n = 8。
计算前缀和 prefix：
prefix = [0, 3, 7, 12, 18, 21, 25, 30, 36]
（prefix[i] 表示前 i 项和，区间和 [i, j] = prefix[j+1] - prefix[i]）
初始化 dp 为 8×8 矩阵，初始值全 0。
按区间长度 len 从 2 到 4（因为环形答案只需区间长度 ≤ n）递推：
- len=2：计算所有长度为 2 的区间，如 [0,1]：
  k=0：dp[0][0] + dp[1][1] + (prefix[2]-prefix[0]) = 0 + 0 + (7-0) = 7
  更新 dp[0][1] = 7。同理计算其他区间。
- len=3：如区间 [0,2]，枚举 k=0 或 k=1：
  - k=0：得分 = dp[0][0] + dp[1][2] + (prefix[3]-prefix[0]) = 0 + (4+5) + (12-0) = 9 + 12 = 21
  - k=1：得分 = dp[0][1] + dp[2][2] + (12-0) = 7 + 0 + 12 = 19
    取最大值 dp[0][2] = 21。
- len=4：如区间 [0,3]（对应环形原问题）：
  枚举 k=0,1,2，计算后得最大值 dp[0][3] = 42（具体计算略）。
遍历所有起点 i（0 到 3），取 dp[i][i+3] 的最大值作为答案。
最终结果：max(dp[0][3], dp[1][4], dp[2][5], dp[3][6])。

关键点

环形问题通过复制数组转为线性问题。
区间 DP 需按长度从小到大计算。
合并得分始终为当前区间石子总数，与划分方式无关。

环形石子合并的最大得分问题题目描述有 n 堆石子排成一个环形，每堆石子的数量用一个数组 stones 表示，其中 stones[i] 表示第 i 堆石子的数量。每次操作可以选择相邻的两堆石子合并为一堆，合并的得分为这两堆石子的数量之和。合并后新堆的石子数为两堆之和，新堆与左右两边的石子堆相邻。重复操作直到只剩下一堆石子。求所有合并操作能获得的最大总得分。示例输入： stones = [3, 4, 5, 6] （环形排列）解释：环形意味着 stones[0] 和 stones[3] 也相邻。解题思路环形处理技巧将环形数组复制一份接在原数组末尾，形成长度为 2n 的线性数组。例如， [3,4,5,6] 扩展为 [3,4,5,6,3,4,5,6] 。这样，原环形的任意连续区间都对应新线性数组中长度为 n 以内的某个区间。状态定义设 dp[i][j] 表示合并线性数组中第 i 到第 j 堆石子（闭区间）所能获得的最大得分。注意：合并后剩余一堆石子，但过程中需要记录区间和，因此需预处理前缀和数组 prefix ，以便快速计算区间和。状态转移方程若区间长度 len = 1 （即 i = j ），只有一堆石子，无需合并，得分 dp[i][j] = 0 。若区间长度 len ≥ 2 ，枚举最后一次合并的分割点 k （ i ≤ k < j ），将区间分为 [i, k] 和 [k+1, j] 。合并这两部分的得分为区间 [i, j] 的石子总数，即 prefix[j+1] - prefix[i] 。转移方程：需遍历所有 k 取最大值。环形答案提取环形问题的最终答案为所有长度为 n 的区间对应的 dp[i][i+n-1] 中的最大值。详细步骤（以示例为例）输入 stones = [3, 4, 5, 6] ， n = 4 。扩展为线性数组： [3,4,5,6,3,4,5,6] ，长度 2n = 8 。计算前缀和 prefix ： prefix = [0, 3, 7, 12, 18, 21, 25, 30, 36] （ prefix[i] 表示前 i 项和，区间和 [i, j] = prefix[j+1] - prefix[i] ）初始化 dp 为 8×8 矩阵，初始值全 0。按区间长度 len 从 2 到 4（因为环形答案只需区间长度 ≤ n）递推： len=2 ：计算所有长度为 2 的区间，如 [0,1] ： k=0 ： dp[0][0] + dp[1][1] + (prefix[2]-prefix[0]) = 0 + 0 + (7-0) = 7 更新 dp[0][1] = 7 。同理计算其他区间。 len=3 ：如区间 [0,2] ，枚举 k=0 或 k=1 ： k=0 ：得分 = dp[0][0] + dp[1][2] + (prefix[3]-prefix[0]) = 0 + (4+5) + (12-0) = 9 + 12 = 21 k=1 ：得分 = dp[0][1] + dp[2][2] + (12-0) = 7 + 0 + 12 = 19 取最大值 dp[0][2] = 21 。 len=4 ：如区间 [0,3] （对应环形原问题）：枚举 k=0,1,2 ，计算后得最大值 dp[0][3] = 42 （具体计算略）。遍历所有起点 i （0 到 3），取 dp[i][i+3] 的最大值作为答案。最终结果： max(dp[0][3], dp[1][4], dp[2][5], dp[3][6]) 。关键点环形问题通过复制数组转为线性问题。区间 DP 需按长度从小到大计算。合并得分始终为当前区间石子总数，与划分方式无关。