环形石子合并问题（最小得分） 题目描述： 有n堆石子排成一个环形，每堆石子有一定的数量。现在需要将这些石子合并成一堆，合并规则是每次只能选择相邻的两堆合并，合并的得分是新的一堆的石子数量。请设计算法计算合并的最小总得分。 解题过程： 问题分析 这是一个经典的区间动态规划问题。由于石子排成环形，我们需要将环形问题转化为线性问题来处理。环形结构可以看作是在线性结构的基础上增加了首尾相连的特性。 环形转线性技巧 对于环形问题，常用的技巧是将原数组复制一份接在后面，形成一个长度为2n的线性数组。这样，环形中的任意一个长度为n的连续子序列都对应这个扩展数组中的一个长度为n的连续子区间。 状态定义 定义dp[ i][ j ]表示合并从第i堆到第j堆石子的最小得分（i和j在扩展数组的索引范围内）。 状态转移方程 对于区间[ i,j]，我们可以枚举最后一次合并的位置k（i ≤ k < j），将区间分成[ i,k]和[ k+1,j ]两部分： dp[ i][ j] = min(dp[ i][ k] + dp[ k+1][ j] + sum[ i][ j ]) 其中sum[ i][ j ]表示从i到j的石子总数。 前缀和优化 为了快速计算区间和，我们预先计算前缀和数组prefix，其中： prefix[ i] = stones[ 0] + stones[ 1] + ... + stones[ i-1 ] 那么sum[ i][ j] = prefix[ j+1] - prefix[ i ] 具体步骤 (1) 将原石子数组复制一份，形成长度为2n的新数组 (2) 计算新数组的前缀和 (3) 初始化dp数组，对于长度为1的区间，dp[ i][ i ] = 0（不需要合并） (4) 按区间长度从小到大计算： 长度len从2到n（因为最后要合并成1堆） 对于每个起始位置i，计算j = i + len - 1 遍历所有可能的分割点k 更新dp[ i][ j ]的最小值 最终答案 由于是环形，我们需要考虑所有可能的起点，最终答案是： min(dp[ i][ i+n-1])，其中0 ≤ i < n 时间复杂度 O(n³)，空间复杂度O(n²) 示例验证 假设有4堆石子[ 1,2,3,4 ]排成环形： 扩展数组为[ 1,2,3,4,1,2,3,4 ] 计算所有长度为4的区间的最小得分 最终找到全局最小值 这种环形转线性的技巧是处理环形区间DP问题的通用方法，可以保证我们考虑到环形结构的所有可能合并顺序。