环形石子合并问题（最小得分版本） 题目描述 给定一个环形数组 stones ，数组中的元素 stones[i] 表示第 i 堆石子的数量。环形数组意味着首尾相连，即 stones[0] 与 stones[n-1] 相邻。每次操作可以选择相邻的两堆石子合并成一堆，合并的成本为这两堆石子的数量之和。重复操作直到所有石子合并成一堆，求合并的最小总成本。 解题过程 问题分析 环形数组的处理：将原数组复制一份接在原数组末尾，形成长度为 2n 的线性数组，这样环形问题转化为线性问题。 区间动态规划定义：设 dp[i][j] 表示合并从第 i 堆到第 j 堆石子的最小成本（区间 [i, j] ）。 状态转移：最后一次合并时，区间 [i, j] 被分成两个子区间 [i, k] 和 [k+1, j] ，合并成本为两个子区间石子总数之和，即 sum(i, j) 。 前缀和优化 预处理前缀和数组 prefix ，使得 prefix[i] 表示前 i 堆石子的总和（索引从1开始），则区间和 sum(i, j) = prefix[j+1] - prefix[i] 。 例如， stones = [1, 3, 2, 4] ，复制后为 [1, 3, 2, 4, 1, 3, 2, 4] ，前缀和需覆盖扩展后的数组。 动态规划步骤 初始化： dp[i][i] = 0 （单堆石子无需合并）。 枚举区间长度 len 从 2 到 n （因为最终需合并成一堆，但环形处理时需计算所有长度为 n 的区间）。 对于每个起点 i ，终点 j = i + len - 1 ，枚举分割点 k （ i ≤ k < j ）： 最终答案：所有长度为 n 的区间的最小 dp[i][i+n-1] （ 0 ≤ i < n ）。 示例演示 输入： stones = [1, 3, 2, 4] ，复制后为 [1, 3, 2, 4, 1, 3, 2, 4] ， n = 4 。 计算前缀和： prefix = [0, 1, 4, 6, 10, 11, 14, 16, 20] 。 区间 [0, 3] ：枚举分割点 k=0,1,2 ，最小成本为 min(0+dp[1][3]+10, dp[0][1]+dp[2][3]+10, ...) ，需逐步计算所有子区间。 最终比较 dp[0][3] 、 dp[1][4] 、 dp[2][5] 、 dp[3][6] ，取最小值。 复杂度分析 时间复杂度：O(n³)，三重循环（区间长度、起点、分割点）。 空间复杂度：O(n²)，存储 dp 表。