Description
There are n piles of stones arranged in a row. The ith pile has stones[i] stones.
A move consists of merging exactly k consecutive piles into one pile, and the cost of this move is equal to the total number of stones in these k piles.
Return the minimum cost to merge all piles of stones into one pile. If it is impossible, return -1.
Example 1:
Input: stones = [3,2,4,1], k = 2
Output: 20
Explanation: We start with [3, 2, 4, 1].
We merge [3, 2] for a cost of 5, and we are left with [5, 4, 1].
We merge [4, 1] for a cost of 5, and we are left with [5, 5].
We merge [5, 5] for a cost of 10, and we are left with [10].
The total cost was 20, and this is the minimum possible.
Example 2:
Input: stones = [3,2,4,1], k = 3
Output: -1
Explanation: After any merge operation, there are 2 piles left, and we can't merge anymore. So the task is impossible.
Example 3:
Input: stones = [3,5,1,2,6], k = 3
Output: 25
Explanation: We start with [3, 5, 1, 2, 6].
We merge [5, 1, 2] for a cost of 8, and we are left with [3, 8, 6].
We merge [3, 8, 6] for a cost of 17, and we are left with [17].
The total cost was 25, and this is the minimum possible.
Constraints:
n == stones.length1 <= n <= 301 <= stones[i] <= 1002 <= k <= 30
Solutions
Solution 1
PythonJavaC++Go
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](code-box)
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];
}
}(code-box)
class Solution {
public:
int mergeStones(vector<int>& stones, int K) {
int n = stones.size();
if ((n - 1) % (K - 1)) {
return -1;
}
int s[n + 1];
s[0] = 0;
for (int i = 1; i <= n; ++i) {
s[i] = s[i - 1] + stones[i - 1];
}
int f[n + 1][n + 1][K + 1];
memset(f, 0x3f, sizeof(f));
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] = 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];
}
};(code-box)
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]
}(code-box)
