环形石子合并的最小得分问题 题目描述： 有n堆石子排成一个环形，每堆石子的数量用数组stones表示，其中stones[ i ]表示第i堆石子的数量。每次操作可以将相邻的两堆石子合并为一堆，合并的代价为这两堆石子的数量之和。请找出将所有石子合并成一堆的最小总代价。 解题过程： 问题分析： 石子排成环形，意味着第一堆和最后一堆石子也是相邻的 每次合并相邻的两堆石子，合并代价为两堆石子数量之和 目标是找到合并顺序使得总代价最小 环形转线性： 由于是环形结构，我们可以将其转化为线性问题。常用的方法是复制数组： 将原数组stones复制一份接在后面，得到长度为2n的新数组 在新数组上考虑所有长度为n的连续子数组，每个子数组对应环形的一种展开方式 动态规划定义： 定义dp[ i][ j ]表示合并第i堆到第j堆石子的最小代价（i ≤ j） 状态转移方程： 当i = j时，只有一堆石子，不需要合并，dp[ i][ j ] = 0 当i < j时，我们需要考虑最后一次合并的位置k（i ≤ k < j） 最后一次合并的代价是i到j所有石子的总和 状态转移方程：dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j ] + sum(i,j))，其中k从i到j-1 前缀和优化： 为了快速计算区间和sum(i,j)，我们可以预处理前缀和数组prefix： prefix[ 0 ] = 0 prefix[ i] = stones[ 0] + stones[ 1] + ... + stones[ i-1 ] sum(i,j) = prefix[ j+1] - prefix[ i ] 计算顺序： 由于dp[ i][ j ]依赖于更短的区间，我们需要按区间长度从小到大计算： 先计算长度为2的区间，然后长度为3，直到长度为n 环形处理： 对于环形问题，我们在长度为2n的数组上计算，然后取所有长度为n的区间的最小值作为答案 算法步骤： 步骤1：如果n=1，直接返回0 步骤2：创建长度为2n的扩展数组 步骤3：计算前缀和数组 步骤4：初始化dp数组，对角线元素为0 步骤5：按区间长度len从2到n遍历 步骤6：对于每个起始位置i，计算结束位置j = i + len - 1 步骤7：遍历所有可能的分割点k，计算最小代价 步骤8：在所有长度为n的区间中找最小值 时间复杂度：O(n³)，空间复杂度：O(n²) 这个算法通过环形转线性的技巧，将复杂的环形问题转化为经典的区间动态规划问题，是处理环形结构问题的典型方法。