LC.P1000[合并石头的最低成本]

题目描述

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

每次移动（move）需要将连续的 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，这是可能的最小值。

提示：

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

方法一：区间DP+记忆化搜索

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    int[][][] cache;
    int[] s;
    int k;

    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) > 0) return -1; // 无法合并成一堆
        s = new int[n + 1];
        for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + stones[i - 1];
        this.k = k;
        cache = new int[n][n][k + 1];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                Arrays.fill(cache[i][j], -1); // -1表示还没计算过
            }
        }
        return dfs(0, n - 1, 1);
    }

    /**
     * 表示把stones[i]~stones[j]合并成p堆的最低成本
     */
    private int dfs(int i, int j, int p) {
        if (cache[i][j][p] != -1) return cache[i][j][p];
        // 合并成一堆
        if (p == 1) {
            // 如果只有一堆，则无需合并，成本为0
            // 否则，计算从i~j合并成k堆的最小成本
            return cache[i][j][p] = i == j ? 0 : dfs(i, j, k) + s[j + 1] - s[i];
        }
        int ans = Integer.MAX_VALUE;
        for (int m = i; m < j; m += k - 1) {
            ans = Math.min(ans, dfs(i, m, 1) + dfs(m + 1, j, p - 1));
        }
        return cache[i][j][p] = ans;
    }
}
  • 时间复杂度：$O(n^3)$
  • 空间复杂度：$O(n^2k)$

方法二：优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    int[][] cache;
    int[] s;
    int k;

    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) > 0) return -1; // 无法合并成一堆
        s = new int[n + 1];
        for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + stones[i - 1];
        this.k = k;
        cache = new int[n][n];
        for (int i = 0; i < n; ++i) {
            Arrays.fill(cache[i], -1); // -1表示还没计算过
        }
        return dfs(0, n - 1);
    }

    private int dfs(int i, int j) {
        if (i == j) return 0;
        if (cache[i][j] != -1) return cache[i][j];
        int ans = Integer.MAX_VALUE;
        for (int m = i; m < j; m += k - 1) {
            ans = Math.min(ans, dfs(i, m) + dfs(m + 1, j));
        }
        if ((j - i) % (k - 1) == 0) {
            // 可以合并成一堆
            ans += s[j + 1] - s[i];
        }
        return cache[i][j] = ans;
    }
}

方法三：1:1翻译成递推

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n - 1) % (k - 1) > 0) return -1; // 无法合并成一堆
        int[] s = new int[n + 1];
        for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + stones[i - 1];
        int[][] f = new int[n][n];
        for (int i = n - 1; i >= 0; --i)
            for (int j = i + 1; j < n; ++j) {
                f[i][j] = Integer.MAX_VALUE;
                for (int m = i; m < j; m += k - 1) {
                    f[i][j] = Math.min(f[i][j], f[i][m] + f[m + 1][j]);
                }
                // 可以合并成一堆
                if ((j - i) % (k - 1) == 0) f[i][j] += s[j + 1] - s[i];
            }
        return f[0][n - 1];
    }
}
  • 时间复杂度：$O(n^3/k)$
  • 空间复杂度：$O(n^2)$