石子合并问题（环形版本） 题目描述 有N堆石子排成一个环形，每堆石子的数量用数组stones表示。每次操作可以将相邻的两堆石子合并成一堆，合并的代价是这两堆石子的数量之和。请找出将所有石子合并成一堆的最小总代价。 解题思路 环形问题可以通过将原数组复制一份接在后面，转化为长度为2N的线性问题 定义dp[ i][ j ]表示合并第i到第j堆石子的最小代价 使用前缀和数组快速计算区间和 遍历所有可能的区间长度和起点，计算最小合并代价 详细步骤 步骤1：处理环形结构 将原数组复制一份：newStones = stones + stones 这样环形问题就转化为长度为2N的线性数组问题 我们需要在长度为N的窗口内寻找最优解 步骤2：定义状态和前缀和 定义dp[ i][ j ]为合并第i到第j堆石子的最小代价 定义前缀和数组preSum，其中preSum[ i ]表示前i堆石子的总和 区间[ i,j]的石子总和为preSum[ j+1] - preSum[ i ] 步骤3：状态转移方程 对于区间[ i,j ]，考虑最后一次合并的位置k 将区间分为[ i,k]和[ k+1,j ]两部分 合并代价 = dp[ i][ k] + dp[ k+1][ j] + (区间[ i,j ]的石子总和) 状态转移方程：dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j ]) + sum(i,j)，其中k从i到j-1 步骤4：初始化边界条件 当区间长度为1时（即i=j），不需要合并，代价为0 当区间长度为2时，合并代价就是两堆石子之和 步骤5：动态规划求解 按区间长度从小到大进行遍历 对于每个起点i，计算终点j = i + len - 1 遍历所有可能的分割点k，找到最小代价 步骤6：寻找最终答案 在转化后的2N数组中，检查所有长度为N的区间 最小代价为min(dp[ i][ i+N-1 ])，其中i从0到N-1 示例分析 假设石子堆为[ 1,2,3,4 ]（环形）： 转化为线性数组：[ 1,2,3,4,1,2,3,4 ] 计算所有长度为4的区间的最小合并代价 最终答案为这些代价中的最小值 这种方法通过复制数组巧妙地将环形问题转化为线性问题，确保了算法的正确性和效率。