题目

有 n 堆石头排成一排，第 i 堆中有 stones[i] 块石头。

每次 移动 需要将 连续的 k 堆石头合并为一堆，而这次移动的成本为这 k 堆中石头的总数。

返回把所有石头合并成一堆的最低成本。如果无法合并成一堆，返回 -1 。

示例 1：

输入：stones = [3,2,4,1], K = 2
输出：20
解释：
从 [3, 2, 4, 1] 开始。
合并 [3, 2]，成本为 5，剩下 [5, 4, 1]。
合并 [4, 1]，成本为 5，剩下 [5, 5]。
合并 [5, 5]，成本为 10，剩下 [10]。
总成本 20，这是可能的最小值。

示例 2：

输入：stones = [3,2,4,1], K = 3
输出：-1
解释：任何合并操作后，都会剩下 2 堆，我们无法再进行合并。所以这项任务是不可能完成的。.

示例 3：

输入：stones = [3,5,1,2,6], K = 3
输出：25
解释：
从 [3, 5, 1, 2, 6] 开始。
合并 [5, 1, 2]，成本为 8，剩下 [3, 8, 6]。
合并 [3, 8, 6]，成本为 17，剩下 [17]。
总成本 25，这是可能的最小值。

提示：

• n == stones.length
• 1 <= n <= 30
• 1 <= stones[i] <= 100
• 2 <= k <= 30

思路

区间DP的做法

解法

class Solution {
    // 区间DP的做法
    public int mergeStones(int[] stones, int step) {
        int n = stones.length;
        if ((n - 1) % (step - 1) != 0) return -1;
        int[] sum = new int[n + 1];
        int[][] f = new int[n][n];
        for (int i = 0; i < n; i++) sum[i + 1] = sum[i] + stones[i];
        for (int j = 1; j < n; j++) {
            for (int i = j - 1; i >= 0; i--) {
                f[i][j] = 0x3f3f3f3f;
                for (int k = i; k < j; k += step - 1) {
                    f[i][j] = Math.min(f[i][j], f[i][k] + f[k + 1][j]);
                }
                if ((j - i) % (step - 1) == 0) f[i][j] += sum[j + 1] - sum[i];
            }
        }
        return f[0][n - 1];
    }
}

总结

• 分析出几种情况，然后分别对各个情况实现