# 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.
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 . The total cost was 20, and this is the minimum possible.
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.
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 . The total cost was 25, and this is the minimum possible.
Approach 1: backtracking (TLE).
Approach 2: DP. Record the cost to merge stones i to j as much as possible.
# Code (Python)
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
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] 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++)