石子合并问题（环形版本） 题目描述： 假设有n堆石子排成一个环形，每堆石子有一定的数量。现在要将这些石子合并成一堆，合并规则是每次只能合并相邻的两堆石子，合并的代价是这两堆石子的数量之和。目标是找到一种合并顺序，使得总合并代价最小。 解题过程： 问题分析： 环形排列意味着第一堆和最后一堆石子也是相邻的 我们需要找到合并顺序，使得总代价最小 这是一个经典的区间动态规划问题 关键思路： 将环形问题转化为线性问题：将原数组复制一份接在后面，这样环形问题就变成了长度为2n的线性问题 对于每个可能的起点，计算长度为n的线性石子合并问题 状态定义： 定义dp[ i][ j ]表示合并从第i堆到第j堆石子的最小代价（i ≤ j） 状态转移方程： 对于区间[ i, j]，我们枚举最后一次合并的位置k（i ≤ k < j）： dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j] + sum[ i][ j ]) 其中sum[ i][ j ]表示从第i堆到第j堆石子的总数 具体步骤： 步骤1：预处理前缀和数组 创建前缀和数组prefix，其中prefix[ i ]表示前i堆石子的总和 这样sum[ i][ j] = prefix[ j] - prefix[ i-1 ] 步骤2：环形转线性 将原石子数组arr复制一份，得到新数组newArr，长度为2n 例如：原数组[ 1,2,3] → 新数组[ 1,2,3,1,2,3 ] 步骤3：动态规划求解 初始化dp表，dp[ i][ i ] = 0（单堆石子不需要合并） 按区间长度从小到大计算： 先计算长度为2的区间 然后计算长度为3的区间 依此类推，直到长度为n 步骤4：寻找最优解 在所有的长度为n的区间[ i, i+n-1]（0 ≤ i < n）中，找到dp[ i][ i+n-1 ]的最小值 示例演示： 假设石子堆为[ 3,4,5,2 ]（环形） 步骤1：扩展数组为[ 3,4,5,2,3,4,5,2 ] 步骤2：计算各个区间的最小代价： 区间[ 0,3 ]：合并顺序3,4,5,2 区间[ 1,4 ]：合并顺序4,5,2,3 区间[ 2,5 ]：合并顺序5,2,3,4 区间[ 3,6 ]：合并顺序2,3,4,5 步骤3：比较所有可能起点的最小代价，取最小值 时间复杂度：O(n³) 需要枚举区间起点、终点和分割点 对于环形版本，需要计算2n长度的数组，但实际有效计算仍然是O(n³) 空间复杂度：O(n²) 需要维护n×n的dp表 这种方法通过环形转线性的技巧，将复杂的环形问题转化为熟悉的线性石子合并问题，是解决环形区间动态规划的经典方法。