题目地址：

https://www.lintcode.com/problem/stone-game-ii/description

给定一圈石头一共$n$堆，每堆石头的质量由数组$A$给出，每次允许将相邻的两堆石头合并，每次合并需要花费的能量是两堆石头的质量之和。问如果要将所有石头合并成一堆，需要花费的最小能量是多少。

思路是动态规划。问题的关键在于如何处理首尾两堆合并的情况。我们采取的办法是，将$A$复制一份连到后面，得一个新数组$B$，也就是说$B[0]=A[0],...,B[n-1]=A[n-1],B[n]=A[0],B[n+1]=A[1],...,B[2n-2]=A[n-2]$，接着对这个$B$考虑长度为$n$的区间合并石堆的最小花费即可。关于算法的正确性，我们只需考虑最后一次合并的时候，左右石堆的左端点和右端点即可。对于$A$的最优合并方式，考虑最后一次合并的两个大石堆，我们可以顺时针来看$A$这个环，取第一个大石堆的顺时针方向的第一个小石堆，和第二个大石堆顺时针方向的最后一个小石堆，这两个小石堆在$A$中的下标一定要么相邻，要么一个是$0$一个是$n-1$，但无论怎样，都可以在$B$中找到对应的长度为$n$的一段，恰好以这两个端点为端点，所以算法是对的。 而对于$B$而言，设$f[i][j]$是合并$B[i:j]$这个区间的石堆需要的最小花费，则可以枚举最后一次合并的分界点来做分类，所以有：$$f[i][j]=\underset{i\le k\le j-1}{\min }\{f[i][k]+f[k+1][j]+\sum _{l=i}^{j}B[l]\}$$最后只需要计算一下$$\underset{j-i+1=n}{\min }f[i][j]$$代码如下：

public class Solution { /** * @param A: An integer array * @return: An integer */ public int stoneGame2(int[] A) { // write your code here if (A == null || A.length == 0) { return 0; } int n = A.length; int[] B = new int[n * 2 - 1]; for (int i = 0; i < B.length; i++) { B[i] = A[i % n]; } A = B; // 求一下前缀和，以方便求区间和 int[] preSum = new int[A.length + 1]; for (int i = 0; i < A.length; i++) { preSum[i + 1] = preSum[i] + A[i]; } int[][] dp = new int[A.length][A.length]; // 枚举区间长度 for (int len = 2; len <= n; len++) { // 枚举左端点 for (int i = 0; i + len - 1 < A.length; i++) { // 算出区间左右端点，并进行计算 int l = i, r = l + len - 1; dp[l][r] = Integer.MAX_VALUE; for (int k = l; k <= r - 1; k++) { dp[l][r] = Math.min(dp[l][r], dp[l][k] + dp[k + 1][r] + preSum[r + 1] - preSum[l]); } } } // 找一下长度为n的区间合并石堆最小消耗 int res = Integer.MAX_VALUE; for (int l = 0; l + n - 1 < A.length; l++) { res = Math.min(res, dp[l][l + n - 1]); } return res; } }

时间复杂度$O(n^3)$，空间$O(n^2)$。