算法面試真題詳解：石子歸并

有一個石子歸并的遊戲。最開始的時候，有n堆石子排成一列，目标是要将所有的石子合并成一堆。合并規則如下：

1. 每一次可以合并相鄰位置的兩堆石子

2. 每次合并的代價為所合并的兩堆石子的重量之和

   求出最小的合并代價。

線上評測位址：

領扣題庫官網

樣例 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問題，我們需要用區間表示狀态來遞推。

更多DP算法真題詳解， 點此免費檢視

設s是表示石頭重量的數組，設fi是将s[i,...,j]的石頭合并成一個所需的最少能量，那麼這個最少能量按照最後一步合并的分界線可以分為以下幾種情況：

1、最後一步是s[i]和s[i+1,...,j]合并，此時需要的最少能量是fi+1+sum(s[i]...s[j]),第一項是合并後者需要的能量，第二項是最後一次合并所需要的能量。s[i]自己隻有一個石頭，不需要合并

2、最後一步是s[i,i+1]和s[i+2,...,j]合并，此時需要的最少能量是fi+fi+2+sum(s[i]...s[j])，第一項是合并前兩個石頭需要的能量，第二項是合并後半區間石頭需要的能量，最後一項是最後一次合并需要的能量；

從上面我們可以看出一個規律，fi應該是所有區間分法中前一半區間的石頭合并需要的總能量加上後半區間的總能量再加上最後一次合并需要的能量

• 求得A的字首和
• 區間長度從2開始枚舉，
• 根據上訴思路可得遞推式
• dpl =min(dpl, dpl + dpj + 1 + sum_a[r + 1] - sum_a[l])
• 記得初始化dpl為一個較大值
• 結果存在dp0中

複雜度分析

• 時間複雜度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];
    }
}           

更多題解參考：

九章官網solution