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.
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.
Constraints:
n == stones.length1 <= n <= 301 <= stones[i] <= 1002 <= k <= 30The key idea for solving #1000 Minimum Cost to Merge Stones is recognizing it as an interval dynamic programming problem. Each operation merges K consecutive piles into one, incurring a cost equal to the total stones in that range. Because merges affect future choices, a greedy strategy does not work.
First, compute a prefix sum array so the total number of stones in any subarray [i, j] can be calculated in constant time. Then define a DP state such as dp[i][j] representing the minimum cost to merge piles from index i to j. You split the interval into smaller subproblems and combine their costs while respecting the rule that only K piles can be merged at once.
An important observation is that a segment can only become one pile when (length - 1) % (K - 1) == 0. By iterating over interval lengths and valid partition points, the algorithm gradually builds the optimal cost for larger segments.
The typical solution runs in about O(n^3) time with O(n^2) space, with optimizations possible due to the merge constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Interval Dynamic Programming with Prefix Sum | O(n^3) | O(n^2) |
| Optimized DP using K-step partitioning | O(n^3 / K) | O(n^2) |
NeetCode
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Prefix sums allow you to compute the total number of stones in any subarray in constant time. This is important because each valid merge operation requires adding the sum of stones in the current interval.
Yes, this problem or similar interval dynamic programming problems are common in FAANG-style interviews. They test a candidate’s understanding of DP state design, interval partitioning, and optimization techniques.
The optimal approach uses interval dynamic programming combined with prefix sums. By defining a DP state for the minimum cost to merge a subarray of piles, you can systematically combine smaller segments while respecting the K-pile merge constraint.
The main structure used is a 2D dynamic programming table that stores the minimum merge cost for each interval. A prefix sum array is also used to efficiently calculate the sum of stones in ranges.