# 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: