环形石子合并的最小得分问题 题目描述 有n堆石子排成一个环形，每堆石子的数量用数组stones表示，其中stones[ i ]表示第i堆石子的数量。每次操作可以将相邻的两堆石子合并为一堆，合并的代价为这两堆石子的数量之和。请计算将n堆石子合并成一堆的最小总代价。 解题过程 问题分析 环形排列意味着第一堆和最后一堆石子也是相邻的 需要找到合并顺序使得总代价最小 这是一个经典的区间动态规划问题 环形转线性 将环形问题转化为线性问题：将原数组复制一份接在后面 例如：环形[ 1,3,2,4] → 线性[ 1,3,2,4,1,3,2,4 ] 在新数组上考虑所有长度为n的连续子数组 动态规划定义 dp[ i][ j ]：合并第i堆到第j堆石子的最小代价 sum[ i][ j ]：第i堆到第j堆石子的总数量 初始化：dp[ i][ i ] = 0（单独一堆不需要合并） 状态转移方程 对于区间[ i,j ]，枚举最后一步合并的分割点k dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j] + sum[ i][ j])，其中i ≤ k < j sum[ i][ j ]可以通过前缀和数组快速计算 算法步骤 构建长度为2n的扩展数组 计算前缀和数组prefix 按区间长度从小到大计算dp值 最终答案为所有长度为n的区间中的最小dp值 复杂度分析 时间复杂度：O(n³) 空间复杂度：O(n²) 示例 对于石子堆[ 1,3,2,4 ]： 扩展为[ 1,3,2,4,1,3,2,4 ] 计算得到最小合并代价为： 先合并(1,3)代价4，再合并(2,4)代价6， 然后合并(4,6)代价10，最后合并(10,4)代价14 总代价=4+6+10=20