We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Minimum Cost to Merge Stones

Difficulty: Hard

Problem Description

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.

Key Insights

  • Merging k consecutive piles reduces the number of piles by k-1.
  • To merge all piles into one, the final number of piles must be exactly 1, which means that (n - 1) must be divisible by (k - 1).
  • The problem can be efficiently solved using dynamic programming combined with prefix sums to store cumulative stone counts.
  • The cost of merging piles needs to be minimized through strategic choices of which piles to merge.

Space and Time Complexity

Time Complexity: O(n^3)
Space Complexity: O(n^2)

Solution

The solution involves using a dynamic programming approach where we maintain a DP table dp[i][j] that represents the minimum cost to merge the stones from the i-th pile to the j-th pile. The prefix sum array is used to calculate the cost of merging any subarray efficiently. The algorithm iterates over all possible lengths of the subarrays and checks for valid merges, updating the DP table accordingly.

Code Solutions

def mergeStones(stones, k):
    n = len(stones)
    if (n - 1) % (k - 1) != 0:
        return -1
    
    # Prefix sums to calculate costs easily
    prefix = [0] * (n + 1)
    for i in range(1, n + 1):
        prefix[i] = prefix[i - 1] + stones[i - 1]

    # DP table
    dp = [[float('inf')] * n for _ in range(n)]
    
    # Cost of merging stones from i to j
    for length in range(1, n + 1):  # Length of the subarray
        for i in range(n - length + 1):
            j = i + length - 1  # End index
            if length == 1:
                dp[i][j] = 0  # No cost to merge a single pile
            else:
                for mid in range(i, j, k - 1):
                    dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j] + prefix[j + 1] - prefix[i])
            # If we can merge completely
            if (length - 1) % (k - 1) == 0:
                dp[i][j] += prefix[j + 1] - prefix[i]

    return dp[0][n - 1]
← Back to All Questions