Minimum Cost to Merge Stones

54.3k
0

An array stones represents piles arranged in a fixed row, and stones[index] gives the number of stones in one pile. A legal move merges exactly K consecutive piles into one pile and charges the total number of stones inside the selected group.

Return the minimum total cost required to leave one pile. Return -1 if the allowed operation cannot reduce the complete row to one pile.

Example 1

Input: stones = [3, 5, 1, 2, 6], K = 3
Output: 25
Explanation: Merge [5, 1, 2] for cost 8, producing [3, 8, 6]. Merge all remaining piles for cost 17. The minimum total cost is 8 + 17 = 25.

Example 2

Input: stones = [3, 2, 4, 1], K = 3
Output: -1
Explanation: One merge leaves two piles, but another legal move needs exactly three consecutive piles. A single final pile cannot be formed.

Recursion

Every legal merge combines K neighboring piles into one, so each merge reduces the number of piles by exactly K - 1. Therefore, reducing N piles to one is possible only when (N - 1) % (K - 1) == 0. Prefix sums are used to find the total stones in any interval in constant time.

We treat each interval as a smaller version of the same problem. The state solve(left, right) finds the minimum cost to reduce stones[left...right] to the fewest piles possible. We try split points in steps of K - 1, ensuring the left part can be reduced appropriately before combining it with the right part. The initial call is solve(0, N - 1), which represents all the original piles.

Algorithm

  • Check (N - 1) % (K - 1). If it is not 0, return -1 because the piles cannot be merged into one.

  • Build a prefix-sum array so the total stones in any interval can be calculated in O(1).

  • Start solve(left, right) with left = 0 and right = N - 1 to cover all piles.

  • Return 0 for a single-pile interval because no merge is needed.

  • Try split points from left to right - 1 in steps of K - 1. This ensures the left interval can be reduced to one pile when required.

  • Add the costs of the left and right recursive subproblems and keep the minimum, because each split represents a different valid way to divide the interval.

  • Add the interval's total stone count only when (length - 1) % (K - 1) == 0, because only then can the interval be merged into one pile.

  • Return the minimum cost found across all valid splits.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the minimum cost for one interval.
int solve(
int left,
int right,
vector<int>& prefix,
int k
) {
// A single pile needs no additional merge.
if (left == right) {
return 0;
}
// A large value accepts the first valid split.
int best = INT_MAX;
// Valid splits leave one pile on the left.
for (
int split = left;
split < right;
split += k - 1
) {
// The left call reduces the left interval.
int leftCost = solve(
left,
split,
prefix,
k
);
// The right call reduces the right interval.
int rightCost = solve(
split + 1,
right,
prefix,
k
);
// Independent interval costs are combined.
int currentCost = leftCost + rightCost;
// Minimum selection keeps the best split.
best = min(best, currentCost);
}
int length = right - left + 1;
// A feasible interval can finish as one pile.
if ((length - 1) % (k - 1) == 0) {
// Prefix sums provide the final merge cost.
int rangeSum =
prefix[right + 1] - prefix[left];
// The final interval merge is paid once.
best += rangeSum;
}
// The best split solves the active interval.
return best;
}
public:
// Returns the minimum cost for all stone piles.
int mergeStones(vector<int>& stones, int k) {
int n = stones.size();
// A nonzero remainder blocks one final pile.
if ((n - 1) % (k - 1) != 0) {
return -1;
}
// Prefix sums support constant-time range sums.
vector<int> prefix(n + 1, 0);
// Every prefix extends by one pile value.
for (int index = 0; index < n; index++) {
prefix[index + 1] =
prefix[index] + stones[index];
}
// Extreme indices represent the complete row.
return solve(0, n - 1, prefix, k);
}
};
// Driver code
int main() {
vector<int> stones = {3, 5, 1, 2, 6};
int k = 3;
Solution obj;
cout << obj.mergeStones(stones, k);
return 0;
}

Complexity Analysis

Time Complexity: O(3N), where N is the number of elements. In the worst case, each interval explores multiple split choices and recursively solves both resulting parts without memoizing repeated interval results.

Space Complexity: O(N), because the prefix-sum array uses O(N) space and the recursion stack can contain at most N nested interval calls.

Memoization

Direct recursion can solve the same (left, right) interval multiple times through different parent splits. Memoization avoids this repeated work by storing the result of each interval in a two-dimensional dp array. When the same interval is reached again, its stored result is returned immediately instead of expanding the recursion again.

The state meaning, valid split stride, and interval-sum rule remain unchanged. Each dp[left][right] entry starts at -1 to indicate that the interval has not been solved yet. Once computed, its nonnegative value represents the minimum cost for that interval.

Algorithm

  • Perform the same feasibility check and build the prefix-sum array, because memoization only avoids repeated recursive calculations.

  • Create an N × N dp array and fill it with -1, so every interval initially represents an unsolved state.

  • Start with solve(0, N - 1) because the initial interval contains all the stone piles.

  • Return 0 for a single-pile interval. If dp[left][right] is already solved, return its stored value to avoid repeated recursion.

  • Try split indices in steps of K - 1, preserving the valid split structure from the recursive approach.

  • Add the costs of the two recursive subproblems and keep the minimum, because each valid split represents a possible partition of the interval.

  • Add the interval sum only when (length - 1) % (K - 1) == 0, because only then can the interval be merged into one pile.

  • Store the computed result in dp[left][right] before returning it, so future calls can reuse the answer.

  • Return the cached result for the complete interval after all reachable states have been solved at most once.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Returns the cached cost for one interval.
int solve(
int left,
int right,
vector<int>& prefix,
int k,
vector<vector<int>>& dp
) {
// A single pile needs no additional merge.
if (left == right) {
return 0;
}
// A saved answer avoids repeated interval work.
if (dp[left][right] != -1) {
return dp[left][right];
}
// A large value accepts the first valid split.
int best = INT_MAX;
// Valid splits leave one pile on the left.
for (
int split = left;
split < right;
split += k - 1
) {
// The left call reuses or solves one range.
int leftCost = solve(
left,
split,
prefix,
k,
dp
);
// The right call reuses or solves one range.
int rightCost = solve(
split + 1,
right,
prefix,
k,
dp
);
// Independent interval costs are combined.
int currentCost = leftCost + rightCost;
// Minimum selection keeps the best split.
best = min(best, currentCost);
}
int length = right - left + 1;
// A feasible interval can finish as one pile.
if ((length - 1) % (k - 1) == 0) {
// Prefix sums provide the final merge cost.
int rangeSum =
prefix[right + 1] - prefix[left];
// The final interval merge is paid once.
best += rangeSum;
}
// Cache storage preserves the interval answer.
dp[left][right] = best;
// The cached value solves the active interval.
return dp[left][right];
}
public:
// Returns the minimum cost for all stone piles.
int mergeStones(vector<int>& stones, int k) {
int n = stones.size();
// A nonzero remainder blocks one final pile.
if ((n - 1) % (k - 1) != 0) {
return -1;
}
// Prefix sums support constant-time range sums.
vector<int> prefix(n + 1, 0);
// Every prefix extends by one pile value.
for (int index = 0; index < n; index++) {
prefix[index + 1] =
prefix[index] + stones[index];
}
// Negative entries mark unsolved intervals.
vector<vector<int>> dp(
n,
vector<int>(n, -1)
);
// Extreme indices represent the complete row.
return solve(0, n - 1, prefix, k, dp);
}
};
// Driver code
int main() {
vector<int> stones = {3, 5, 1, 2, 6};
int k = 3;
Solution obj;
cout << obj.mergeStones(stones, k);
return 0;
}

Complexity Analysis

Time Complexity: O(N3), where N is the number of elements, because at most O(N2) interval states are computed once and each state checks up to N valid split positions.

Space Complexity: O(N2), because the dp table stores all interval states, while the prefix-sum array and recursion stack each add only O(N) space.

Tabulation

Memoization solves interval states when recursive calls request them, while tabulation fills the same states in increasing order of interval length. This ensures that when a larger interval is processed, all smaller intervals needed for its transitions have already been computed.

Single-pile intervals have a cost of 0. For each larger interval, we try the same valid split points as before, combine the optimal costs of the two subintervals, and add the interval sum only when that interval can be merged into one pile.

A separate Space Optimization approach is not practical for this standard interval DP recurrence. Each larger interval may need values from many different rows and columns of the dp table, so removing previously computed intervals would lose information required by future transitions.

Algorithm

  • Perform the feasibility check and build the prefix-sum array, because impossible pile counts can be rejected immediately and range sums are needed for final merges.

  • Create an N × N dp array initialized with 0, because every single-pile interval has a merge cost of 0.

  • Process interval lengths from 2 to N, ensuring all smaller intervals are computed before a larger interval uses them.

  • Move left across all intervals of the current length and calculate right = left + length - 1, because each (left, right) pair represents one interval state.

  • Try split indices from left in steps of K - 1, preserving the valid partition structure used in the recursive approaches.

  • Calculate dp[left][split] + dp[split + 1][right] and keep the minimum, because each split combines optimal costs from the two subintervals.

  • Add the interval's total sum only when (length - 1) % (K - 1) == 0, because only then can the interval be merged into one pile.

  • Return dp[0][N - 1], because this entry represents the minimum cost to merge the complete row of piles.

Dry Run

Minimum Cost to Merge Stones Tabulation

Minimum Cost to Merge Stones Tabulation

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Returns the minimum cost for all stone piles.
int mergeStones(vector<int>& stones, int k) {
int n = stones.size();
// A nonzero remainder blocks one final pile.
if ((n - 1) % (k - 1) != 0) {
return -1;
}
// Prefix sums support constant-time range sums.
vector<int> prefix(n + 1, 0);
// Every prefix extends by one pile value.
for (int index = 0; index < n; index++) {
prefix[index + 1] =
prefix[index] + stones[index];
}
// Diagonal zeroes represent single piles.
vector<vector<int>> dp(
n,
vector<int>(n, 0)
);
// Shorter intervals prepare longer intervals.
for (int length = 2; length <= n; length++) {
// Every left boundary defines one interval.
for (
int left = 0;
left + length <= n;
left++
) {
int right = left + length - 1;
// A large value accepts the first split.
int best = INT_MAX;
// Valid splits leave one pile on the left.
for (
int split = left;
split < right;
split += k - 1
) {
// Stored sides form one candidate.
int currentCost =
dp[left][split]
+ dp[split + 1][right];
// Minimum selection keeps the best split.
best = min(best, currentCost);
}
// A feasible interval can finish as one pile.
if ((length - 1) % (k - 1) == 0) {
// Prefix sums give the final merge cost.
int rangeSum =
prefix[right + 1]
- prefix[left];
// The final interval merge is paid once.
best += rangeSum;
}
// Table storage completes the interval.
dp[left][right] = best;
}
}
// The outer interval contains the final answer.
return dp[0][n - 1];
}
};
// Driver code
int main() {
vector<int> stones = {3, 5, 1, 2, 6};
int k = 3;
Solution obj;
cout << obj.mergeStones(stones, k);
return 0;
}

Complexity Analysis

Time Complexity: O(N2), where N is the number of elements, because the DP table contains O(N2) intervals and each interval checks up to N possible split positions.

Space Complexity: O(N2), because the interval dp table stores O(N2) values and dominates the O(N) prefix-sum array, while the iterative approach uses no recursion stack.

Interview follow-up Questions

Every merge replaces K piles with one pile and therefore removes exactly K - 1 piles. Reaching one pile from n piles requires an exact number of such reductions.

Dynamic Programming

Read Similar Blogs

Dynamic Programming

Print Longest Increasing Subsequence

Given an integer array arr , find one longest subsequence with values appearing in strictly increasing order. A subsequence keeps the original relative order but may skip any number of elements. Re...

115.1k
Dynamic Programming

Best Time to Buy and Sell Stock IV: At Most K Transactions

Given an integer k and an array prices , prices[day] stores the stock price on a particular day. At most k transactions may be completed. One transaction contains one buy followed by...

50.8k
Dynamic Programming

Best Time to Buy and Sell Stock with Transaction Fee

An array prices stores a stock price for each day, and an integer fee gives the cost of one completed transaction. Any number of transactions may be completed, but only one share may be held at a t...

65.7k
Comments0