Algorithm
Problem Name: 1000. Minimum Cost to Merge Stones
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
Code Examples
#1 Code Example with Javascript Programming
Code -
Javascript Programming
const mergeStones = function(stones, K) {
const KMO = K - 1
const N = stones.length
if ((N - 1) % KMO !== 0) return -1
const sum = [0]
const dp = stones.map(s => stones.map(s1 => 0))
stones.forEach(s => {
sum.push(sum[sum.length - 1] + s)
})
for (let e = KMO; e < N; e++) {
for (let b = e - KMO; b >= 0; b--) {
for (let split = e - 1; split >= b; split -= KMO) {
let cost = dp[b][split] + dp[split + 1][e]
dp[b][e] = dp[b][e] === 0 ? cost : Math.min(dp[b][e], cost)
}
if ((e - b) % KMO === 0) {
dp[b][e] += sum[e + 1] - sum[b]
}
}
}
return dp[0][N - 1]
}
Input
stones = [3,2,4,1], k = 2
Output
20
#2 Code Example with Python Programming
Code -
Python Programming
class Solution:
def mergeStones(self, stones, K):
n = len(stones)
if (n - 1) % (K - 1): return -1
prefix = [0] * (n + 1)
for i in range(n):
prefix[i + 1] = prefix[i] + stones[i]
import functools
@functools.lru_cache(None)
def dp(i, j):
if j - i + 1 < K: return 0
res = min(dp(i, mid) + dp(mid + 1, j) for mid in range(i, j, K - 1))
if (j - i) % (K - 1) == 0:
res += prefix[j + 1] - prefix[i]
return res
return dp(0, n - 1)
Input
stones = [3,2,4,1], k = 2
Output
20