石子合并问题（环形版本） 题目描述 有 N 堆石子排成一个环形，每堆石子的数量用数组 a 表示。每次可以选择相邻的两堆石子合并成一堆，合并的代价是这两堆石子的数量之和。问合并成一堆石子的总代价的最小值和最大值分别是多少？ 解题思路 环形问题转化为线性问题：将环形数组复制一份接在原数组末尾，形成长度为 2N 的线性数组。这样，环形中的任意连续 N 堆石子都对应线性数组中的一段连续子数组。 定义状态：设 dp_ min[ i][ j] 表示合并第 i 堆到第 j 堆石子的最小代价，dp_ max[ i][ j ] 表示最大代价。 前缀和预处理：计算前缀和数组 prefix，使得 prefix[ i ] 表示前 i 堆石子的总数量，方便快速计算区间和。 状态转移：枚举区间长度 len 从 2 到 N（len=1 时代价为 0），枚举起点 i，计算终点 j=i+len-1，再枚举分割点 k（i ≤ k < j），将区间 [ i,j] 分成 [ i,k] 和 [ k+1,j] 两部分，合并代价为区间 [ i,j] 的石子总数（即 prefix[ j]-prefix[ i-1 ]）。 最小代价：dp_ min[ i][ j] = min(dp_ min[ i][ k] + dp_ min[ k+1][ j ] + sum(i,j)) 最大代价：dp_ max[ i][ j] = max(dp_ max[ i][ k] + dp_ max[ k+1][ j ] + sum(i,j)) 环形处理：对线性数组的每个长度为 N 的区间 [ i, i+N-1]（i 从 1 到 N）计算 dp_ min 和 dp_ max，最终答案取所有区间的最小值（或最大值）中的最小值（或最大值）。 示例（N=4，石子数 [ 4,5,9,4]） 环形转线性：扩展为 [ 4,5,9,4,4,5,9,4 ]。 计算前缀和：prefix = [ 0,4,9,18,22,26,31,40,44 ]。 区间 DP 计算后，发现最小代价为 43（合并顺序影响结果），最大代价为 54。 最终输出：min=43, max=54。 通过上述步骤，环形石子合并问题被转化为多个线性问题求解，确保结果正确。