九章算法 | 微软面试题：石子归并

有一个石子归并的游戏。最开始的时候，有n堆石子排成一列，目标是要将所有的石子合并成一堆。合并规则如下：

1. 每一次可以合并相邻位置的两堆石子
2. 每次合并的代价为所合并的两堆石子的重量之和

求出最小的合并代价。

在线评测地址：LintCode 领扣

样例 1:

输入: [3, 4, 3]
输出: 17

样例 2:

输入: [4, 1, 1, 4]
输出: 18
解释: 
 1. 合并第二堆和第三堆 => [4, 2, 4], score = 2
 2. 合并前两堆 => [6, 4]，score = 8
 3. 合并剩余的两堆 => [10], score = 18 

算法：区间DP

这是一道区间​DP​问题，我们需要用区间表示状态来递推。设​s​是表示石头重量的数组，设​f[i][j]​是将​s[i,...,j]​的石头合并成一个所需的最少能量，那么这个最少能量按照最后一步合并的分界线可以分为以下几种情况：

1、最后一步是​s[i]​和​s[i+1,...,j]​合并，此时需要的最少能量是​f[i+1][j]+sum(s[i]...s[j])​,第一项是合并后者需要的能量，第二项是最后一次合并所需要的能量。​s[i]​自己只有一个石头，不需要合并

2、最后一步是​s[i,i+1]​和​s[i+2,...,j]​合并，此时需要的最少能量是​f[i][i+1]+f[i+2][j]+sum(s[i]...s[j])​，第一项是合并前两个石头需要的能量，第二项是合并后半区间石头需要的能量，最后一项是最后一次合并需要的能量；

从上面我们可以看出一个规律，​f[i][j]​应该是所有区间分法中前一半区间的石头合并需要的总能量加上后半区间的总能量再加上最后一次合并需要的能量

• 求得​A​的前缀和
• 区间长度从​2​开始枚举，
• 根据上诉思路可得递推式
• ​dp[l][r] =min(dp[l][r], dp[l][j] + dp[j + 1][r] + sum_a[r + 1] - sum_a[l])​
• 记得初始化​dp[l][r]​为一个较大值
• 结果存在​dp[0][size-1]​中

复杂度分析

• 时间复杂度​O(n^3)​
  • 区间​dp​的复杂度
• 空间复杂度​O(n^2)​
  • ​dp​数组的大小

public class Solution {
    /**
     * @param A: An integer array
     * @return: An integer
     */
    public int stoneGame(int[] A) {
        int size = A.length;
        if (A == null || size == 0) {
            return 0;
        }
        
        int[][] dp = new int[size][size];
        int[] sum_a = new int[size + 1];
        //前缀和
        for (int i = 0; i < size; i++) {
            sum_a[i + 1] = sum_a[i] + A[i];
        }
        // 长度从2开始即可，因为长度为1的时候结果是0，dp初始化的时候默认就是0，没必要赋值
        for (int len = 2; len <= size; len++) {
            // i枚举的是正在枚举的区间的左端点
            for (int i = 0; i + len - 1 < size; i++) {
                // 正在枚举的区间左端点是i，右端点是i + size - 1
                int l = i, r = i + len - 1;
                // 在求最小的时候，需要初始化成一个很大的数，然后不断更新
                dp[l][r] = Integer.MAX_VALUE;
                for (int j = l; j < r; j++) {
                    //递推式
                    dp[l][r] = Math.min(dp[l][r], dp[l][j] + dp[j + 1][r] + sum_a[r + 1] - sum_a[l]);
                }
            }
        }
        
        return dp[0][size-1];
    }
}

更多题解参考：九章算法