环形石子合并的最大得分问题 题目描述： 有n堆石子排成一个环形，每堆石子的数量用数组stones表示，其中stones[ i ]表示第i堆石子的数量。每次操作可以将相邻的两堆石子合并为一堆，合并的得分是新一堆石子的数量（即两堆石子数量之和）。重复这个过程直到所有石子合并成一堆。请计算所有合并方案中能获得的最大总得分。 解题过程： 问题分析：这是一个经典的区间动态规划问题。由于石子排成环形，我们需要将环形问题转化为线性问题。常用的方法是将原数组复制一份接在后面，这样长度为2n的线性数组就包含了所有可能的环形区间。 状态定义：定义dp[ i][ j]表示将区间[ i,j ]内的所有石子合并成一堆能获得的最大得分。 状态转移方程： 当i = j时，只有一堆石子，不需要合并，得分为0 当i < j时，我们需要在区间[ i,j]内找到一个分割点k(i ≤ k < j)，将区间分成[ i,k]和[ k+1,j ]两部分 合并得分为：dp[ i][ k] + dp[ k+1][ j ] + sum(i,j) 其中sum(i,j)表示区间[ i,j ]内所有石子的数量之和 预处理前缀和：为了快速计算区间和，我们需要预处理前缀和数组prefix，其中prefix[ i ]表示前i堆石子的数量和。 环形处理：将原数组复制一份，形成长度为2n的新数组，然后在这个长度为2n的数组上进行动态规划。 最终答案：在所有的长度为n的区间中，找出最大的dp值。 具体步骤： 如果n=1，直接返回0（只有一堆石子，不需要合并） 创建长度为2n的新数组newStones，将原数组复制两份 计算前缀和数组prefix，长度为2n+1 初始化dp数组为0 按区间长度从2到n进行遍历（因为长度为1的区间得分为0） 对于每个区间长度len，遍历所有起始位置i 计算结束位置j = i + len - 1 遍历所有可能的分割点k 更新dp[ i][ j] = max(dp[ i][ j], dp[ i][ k] + dp[ k+1][ j] + prefix[ j+1] - prefix[ i ]) 在所有长度为n的区间中找出最大值 时间复杂度：O(n³)，空间复杂度：O(n²)