LeetCode 1000 - Minimum Cost to Merge Stones

The problem asks us to merge n piles of stones into a single pile under a very specific merging rule. Each pile is represented as an integer in the array stones, where stones[i] is the number of stones in the i-th pile.

leetcodehardarraydynamic-programmingprefix-sum

LeetCode Problem 1000

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming, Prefix Sum

Solution

Problem Understanding

The problem asks us to merge n piles of stones into a single pile under a very specific merging rule. Each pile is represented as an integer in the array stones, where stones[i] is the number of stones in the i-th pile. We are allowed to merge exactly k consecutive piles at a time, and the cost of a merge is the sum of stones in those k piles. After each merge, the k piles become a single pile with their total number of stones. The goal is to compute the minimum total cost to merge all piles into one. If it is impossible to reduce to a single pile given k, the function should return -1.

The constraints tell us that the array length n is at most 30, and each pile has at least 1 stone and at most 100 stones. This small input size hints that a dynamic programming solution with cubic time complexity could be feasible.

A critical observation is that it is impossible to end with a single pile unless (n - 1) % (k - 1) == 0. This comes from the fact that every merge reduces the number of piles by k - 1. If this condition is not satisfied, merging to one pile is impossible.

Important edge cases include arrays where k is equal to n (can merge all at once), k is larger than any remaining segment during merging, or arrays where (n - 1) % (k - 1) != 0, which makes the task impossible.

Approaches

Brute Force

A brute-force approach would recursively attempt all valid sequences of merges, summing the costs for each. At every recursive call, we would try merging every possible group of k consecutive piles, calculate the cost, reduce the array, and continue recursively. While correct, this approach has exponential complexity because it explores every possible merge order, which is infeasible even for n = 30.

Optimal Approach

The key insight is to use dynamic programming with prefix sums. Define dp[i][j] as the minimum cost to merge stones from index i to j into as few piles as possible. The transition considers all possible splits m in [i, j) with step k - 1, computing dp[i][m] + dp[m+1][j]. Only when the number of piles in the range can be reduced to exactly one (i.e., (j - i) % (k - 1) == 0) do we add the sum of stones in [i, j] as the cost of the final merge. Using prefix sums allows us to compute the total stones in any interval in O(1) time.

This DP solution leverages the constraint n <= 30, giving a cubic time complexity that is acceptable.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^n) O(n) Explore all merge orders recursively, too slow
Optimal O(n^3 / k) O(n^2) DP with prefix sums and restricted splits based on k

Algorithm Walkthrough

  1. Check feasibility: If (n - 1) % (k - 1) != 0, return -1 immediately because merging to a single pile is impossible.
  2. Compute prefix sums: Construct prefix[i] as the sum of the first i stones. This allows O(1) calculation of the sum of any interval.
  3. Initialize DP table: Let dp[i][j] represent the minimum cost to merge stones[i..j] into the minimal possible number of piles. Initialize dp[i][i] = 0 because a single pile costs nothing.
  4. Fill DP table: For all intervals of length l from 2 to n, iterate through all possible splits m such that m = i + t * (k - 1) for t = 1, 2, ... to ensure valid splits. Update dp[i][j] = min(dp[i][m] + dp[m+1][j]).
  5. Merge interval if possible: If (j - i) % (k - 1) == 0, the interval [i..j] can be merged into a single pile. Add the sum of stones in the interval to dp[i][j].
  6. Return result: dp[0][n-1] contains the minimum total cost to merge the entire array into one pile.

Why it works: The DP table maintains the invariant that dp[i][j] is the minimum cost to merge the interval [i..j] into as few piles as possible. By considering splits at intervals of k - 1, we respect the merge rules and ensure no illegal merges occur. Prefix sums guarantee O(1) computation of interval sums, ensuring correctness and efficiency.

Python Solution

from typing import List

class Solution:
    def mergeStones(self, stones: List[int], k: int) -> int:
        n = len(stones)
        if (n - 1) % (k - 1) != 0:
            return -1
        
        prefix = [0] * (n + 1)
        for i in range(n):
            prefix[i+1] = prefix[i] + stones[i]
        
        dp = [[0] * n for _ in range(n)]
        
        for length in range(2, n + 1):
            for i in range(n - length + 1):
                j = i + length - 1
                dp[i][j] = float('inf')
                for m in range(i, j, k - 1):
                    dp[i][j] = min(dp[i][j], dp[i][m] + dp[m+1][j])
                if (length - 1) % (k - 1) == 0:
                    dp[i][j] += prefix[j+1] - prefix[i]
        
        return dp[0][n-1]

The Python solution first checks feasibility, computes prefix sums for interval sums, and initializes the DP table. It then fills the DP table by considering all valid splits according to k - 1. The final result is read from dp[0][n-1].

Go Solution

func mergeStones(stones []int, k int) int {
    n := len(stones)
    if (n-1)%(k-1) != 0 {
        return -1
    }
    
    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + stones[i]
    }
    
    dp := make([][]int, n)
    for i := 0; i < n; i++ {
        dp[i] = make([]int, n)
    }
    
    for length := 2; length <= n; length++ {
        for i := 0; i <= n-length; i++ {
            j := i + length - 1
            dp[i][j] = 1<<31 - 1
            for m := i; m < j; m += k - 1 {
                if dp[i][m]+dp[m+1][j] < dp[i][j] {
                    dp[i][j] = dp[i][m] + dp[m+1][j]
                }
            }
            if (length-1)%(k-1) == 0 {
                dp[i][j] += prefix[j+1] - prefix[i]
            }
        }
    }
    
    return dp[0][n-1]
}

The Go solution mirrors the Python logic. Go requires careful slice initialization and explicit handling of integer max values. The prefix sums and DP updates follow the same pattern, ensuring correctness.

Worked Examples

Example 1: stones = [3,2,4,1], k = 2

Step Remaining Piles Merge Cost Total Cost
1 [3,2,4,1] Merge [3,2] 5 5
2 [5,4,1] Merge [4,1] 5 10
3 [5,5] Merge [5,5] 10 20

Example 2: stones = [3,2,4,1], k = 3

Cannot merge to single pile, output -1.

Example 3: stones = [3,5,1,2,6], k = 3

Step Remaining Piles Merge Cost Total Cost
1 [3,5,1,2,6] Merge [5,1,2] 8 8
2 [3,8,6] Merge [3,8,6] 17 25

Complexity Analysis

Measure Complexity Explanation
Time O(n^3 / k) Three nested loops: interval length, start index, and split points every k-1
Space O(n^2) DP table of size n x n, plus prefix sum array of size