题目地址：

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

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

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

本文地址：https://blog.csdn.net/qq_46105170/article/details/109221921

【Lintcode】593. Stone Game II

题目地址：

相关推荐