# 1000. Minimum Cost to Merge Stones
CThere are N piles of stones arranged in a row. The i-th 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.
Find 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.
# Solution
Approach 1: backtracking (TLE).
Approach 2: DP. Record the cost to merge stones i to j as much as possible.
# Code (Python)
Approach 1:
def mergeStones(self, stones: List[int], K: int) -> int:
if len(stones) == 1:
return 0
# every merge decreases the number of piles by (K-1)
if K > 2 and len(stones) % (K-1) != 1:
return -1
# backtracking (TLE)
return self._merge(stones, K, 0)
def _merge(self, stones, K, existing_cost):
if len(stones) == 1:
return existing_cost
start = 0
min_cost = float('inf')
while start + K - 1 < len(stones):
# merge (start, start + 1, ..., start + K - 1)
cost = sum(stones[start:start+K])
min_cost = min(min_cost, self._merge(stones[:start] + [cost] + stones[start+K:], K, cost + existing_cost))
start += 1
return min_cost
Approach 2:
def mergeStones(self, stones: List[int], K: int) -> int:
if len(stones) == 1:
return 0
# every merge decreases the number of piles by (K-1)
if K > 2 and len(stones) % (K-1) != 1:
return -1
# preprocess the cumulative sums
cum_sum = [stones[0]]
for stone in stones[1:]:
cum_sum.append(cum_sum[-1] + stone)
# DP: cost[i][j] -- cost to merge stones[i:j+1] as far as possible (at most K-1 piles)
@functools.lru_cache(None)
def merge(i, j):
# already merged
if j - i + 1 < K:
return 0
# use mid to divide into 2 separate chunks, then merge them separately
# make sure the first chunk can be merged into a single pile (thus step size = K - 1) because otherwise it could happen that neither chunk can be merged, e.g. [1,2,3,4] for K = 3, when mid = 1
cost = min(merge(i, mid) + merge(mid + 1, j) for mid in range(i, j, K-1))
# then merge both chunks together if they add up to K piles
if (j - i) % (K - 1) == 0:
#"if (j - i + 1) % (K - 1) == 1" doesn't work for K = 2
cost += cum_sum[j] - cum_sum[i-1] if i != 0 else cum_sum[j]
return cost
return merge(0, len(stones) - 1)
# Code (C++)
Approach 1:
Approach 2: