环形石子合并的最大得分问题（进阶版：带权值） 题目描述 给定一个环形数组 stones ，数组长度为 n ，其中 stones[i] 表示第 i 堆石子的数量。环形数组意味着 stones[0] 和 stones[n-1] 相邻。每次可以合并相邻的两堆石子，合并成本为这两堆石子的数量之和，合并后的新堆石子数量为原两堆之和。合并过程重复 n-1 次，直到所有石子合并为一堆。求合并过程中能获得的最大总得分（即累计成本的最大值）。 进阶条件 ： 每堆石子附带一个权重 weight[i] ，合并两堆石子时，合并成本为 (stones[i] + stones[j]) * (weight[i] + weight[j]) 。求最大总得分。 解题思路 环形处理技巧 ：将环形数组复制一份接在原数组末尾，转化为长度为 2n 的线性数组，枚举所有起点长度为 n 的区间。 状态定义 ： dp[i][j] 表示合并区间 [i, j] 内的石子堆能获得的最大得分。 sum[i][j] 表示区间 [i, j] 内石子总数（用于基础版）。 进阶版需额外记录区间内石子总权重 wSum[i][j] 。 状态转移 ： 枚举分割点 k （ i ≤ k < j ），将区间 [i, j] 拆分为 [i, k] 和 [k+1, j] 。 基础版合并成本为 sum[i][k] + sum[k+1][j] 。 进阶版合并成本为 (sum[i][k] + sum[k+1][j]) * (wSum[i][k] + wSum[k+1][j]) 。 转移方程： 初始化 ：单堆石子合并成本为0（无需合并），即 dp[i][i] = 0 。 计算顺序 ：按区间长度从小到大计算。 详细步骤（以进阶版为例） 预处理 ： 将原数组 stones 和权重数组 weights 分别复制为长度 2n 的数组。 计算前缀和数组 prefixStones 和 prefixWeights ，用于快速查询区间和。 动态规划表填充 ： 遍历区间长度 len 从 2 到 n （因为最终需合并成长度为 n 的区间）。 遍历起点 i （ 0 ≤ i < 2n ），终点 j = i + len - 1 （ j < 2n ）。 初始化 dp[i][j] = -∞ （求最大值）。 枚举分割点 k 从 i 到 j-1 ： 计算左区间石子和 sLeft = prefixStones[k] - prefixStones[i-1] （注意边界）。 计算右区间石子和 sRight = prefixStones[j] - prefixStones[k] 。 同理计算权重和 wLeft 、 wRight 。 合并成本 cost = (sLeft + sRight) * (wLeft + wRight) 。 更新 dp[i][j] = max(dp[i][j], dp[i][k] + dp[k+1][j] + cost) 。 结果提取 ： 遍历所有起点 i （ 0 ≤ i < n ），取 dp[i][i+n-1] 的最大值。 示例（基础版简化演示） 假设 stones = [1, 2, 3] ，环形处理为 [1, 2, 3, 1, 2, 3] 。 区间 [0,2] ：合并顺序 (1+2)=3 ，成本3；再 (3+3)=6 ，总成本 3+6=9 。 区间 [1,3] ：合并顺序 (2+3)=5 ，成本5；再 (5+1)=6 ，总成本 5+6=11 。 最终取所有起点区间的最大值。 进阶版 需在合并成本计算中引入权重乘积，逻辑类似但需维护权重和。 关键点 环形转线性是通用技巧。 进阶版需同步维护石子数量和权重的区间和。 时间复杂度 O(n³)，空间复杂度 O(n²)。