class Solution {
public:
int mergeStones(vector<int>& stones, int k) {
}
};
1000. 合并石头的最低成本
有 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 <= 302 <= K <= 301 <= stones[i] <= 100原站题解
java 解法, 执行用时: 6 ms, 内存消耗: 41 MB, 提交时间: 2023-04-04 09:22:43
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 + 1][n + 1][K + 1];
final int inf = 1 << 20;
for (int[][] g : f) {
for(int[] e : g) {
Arrays.fill(e, inf);
}
}
for (int i = 1; i <= n; ++i) {
f[i][i][1] = 0;
}
for (int l = 2; l <= n; ++l) {
for (int i = 1; i + l - 1 <= n; ++i) {
int j = i + l - 1;
for (int k = 1; k <= K; ++k) {
for (int h = i; h < j; ++h) {
f[i][j][k] = Math.min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1]);
}
}
f[i][j][1] = f[i][j][K] + s[j] - s[i - 1];
}
}
return f[1][n][1];
}
}
golang 解法, 执行用时: 0 ms, 内存消耗: 4.9 MB, 提交时间: 2023-04-04 09:22:25
func mergeStones(stones []int, K int) int {
n := len(stones)
if (n-1)%(K-1) != 0 {
return -1
}
s := make([]int, n+1)
for i, x := range stones {
s[i+1] = s[i] + x
}
f := make([][][]int, n+1)
for i := range f {
f[i] = make([][]int, n+1)
for j := range f[i] {
f[i][j] = make([]int, K+1)
for k := range f[i][j] {
f[i][j][k] = 1 << 20
}
}
}
for i := 1; i <= n; i++ {
f[i][i][1] = 0
}
for l := 2; l <= n; l++ {
for i := 1; i <= n-l+1; i++ {
j := i + l - 1
for k := 2; k <= K; k++ {
for h := i; h < j; h++ {
f[i][j][k] = min(f[i][j][k], f[i][h][k-1]+f[h+1][j][1])
}
}
f[i][j][1] = f[i][j][K] + s[j] - s[i-1]
}
}
return f[1][n][1]
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
python3 解法, 执行用时: 344 ms, 内存消耗: 15.5 MB, 提交时间: 2023-04-04 09:22:09
'''
f[i][j][k]: 区间[i, j] 合并成k堆的最小代价
'''
class Solution:
def mergeStones(self, stones: List[int], K: int) -> int:
n = len(stones)
if (n - 1) % (K - 1):
return -1
s = list(accumulate(stones, initial=0))
f = [[[inf] * (K + 1) for _ in range(n + 1)] for _ in range(n + 1)]
for i in range(1, n + 1):
f[i][i][1] = 0
for l in range(2, n + 1):
for i in range(1, n - l + 2):
j = i + l - 1
for k in range(1, K + 1):
for h in range(i, j):
f[i][j][k] = min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1])
f[i][j][1] = f[i][j][K] + s[j] - s[i - 1]
return f[1][n][1]