1000. Minimum Cost to Merge Stones
Problem Description
In this problem, we are given n
piles of stones arranged in a row. Each pile contains a certain number of stones, given by the array stones
where stones[i]
represents the number of stones in the i-th
pile. We can perform a move that merges k
consecutive piles into a single pile. The cost of such a move is equal to the sum of stones in the k
piles that were merged.
The objective is to find the minimum cost to merge all the piles into one. However, there is a constraint: we can only merge exactly k
consecutive piles at a time. If it is not possible to merge all piles into one, considering this constraint, we should return -1
. This adds a twist to the problem because we cannot simply merge any number of piles; it has to be exactly k
piles each time.
Intuition
The solution to this problem makes use of dynamic programming. The intuition behind the approach is to break down the problem into smaller subproblems, solve each subproblem, and use the results to build up the solution to the final problem.
Since the costs are dependent on consecutive piles and the number of stones in the piles that are merged, it makes sense to consider:
- The subproblem of finding the minimal cost to merge a subsequence of piles into a fewer number of piles.
- Then gradually increase the number of piles being considered until we reach the full list of piles.
However, there are additional points to consider:
- If
(n - 1) % (K - 1)
is not zero, we cannot merge into exactly one pile since at some point the number of piles left cannot be merged by groups ofk
. Therefore, we return-1
. - We use a 3D dynamic programming table
f
, wheref[i][j][k]
represents the minimum cost to merge the piles fromi
toj
intok
piles.
We perform the following steps:
- Precompute the prefix sum array to quickly calculate the sum of stones from any pile
i
to any pilej
. - Initialize the table
f[i][i][1]
to0
because the cost to merge a single pile into a single pile is0
. - Use a bottom-up approach to solve all subproblems starting from the lowest number of piles and expanding to the full list.
- Update
f[i][j][k]
by considering the cost of merging a certain number of piles and check if adding an additional pile to those already merged is beneficial. - To merge piles into one, we look at the result of merging
k
piles and add the cost of all stones fromi
toj
, stored in the prefix sum array.
The answer to the problem will be stored in f[1][n][1]
, which represents the minimal cost of merging all piles from 1 to n into a single pile.
Learn more about Dynamic Programming and Prefix Sum patterns.
Solution Approach
The solution uses a 3D dynamic programming (DP) table to keep track of the minimum cost for various subproblems, as well as a prefix sum array to efficiently calculate the total number of stones in a range of piles.
Here is a step-by-step explanation of the solution approach:
-
Initialization: First, we check if the total number of piles
n
allows them to be merged into one. Since every merge reduces the number of piles byK - 1
, if(n - 1) % (K - 1)
is not zero, it's impossible to end with one pile, and we return-1
. -
Prefix Sum Array: The prefix sum array
s
is prepared, wheres[0]
is set to0
ands[i]
is the total number of stones from pile1
toi
inclusive. This allows quick calculation of the total number of stones in any rangei
toj
by simply doings[j] - s[i - 1]
. -
DP Table: The 3D DP array
f
is created and filled with infinity (inf
) to denote that we have not calculated the minimal cost for the given subproblems yet.f[i][i][1]
is set to0
for alli
since there is no cost to "merge" a single pile into itself. -
Subproblem Solutions: Next, the nested loops iterate through all subranges
l
of piles from length2
ton
(n
being the full range). For each subrange, we calculate the cost of merging subranges intok
piles where1 <= k <= K
. -
Transition: Inside another nested loop, we calculate
f[i][j][k]
by iterating over all possible middle pointsh
. The costf[i][j][k]
is updated as the minimum off[i][j][k]
or the sum of costsf[i][h][1]
andf[h + 1][j][k - 1]
. This represents merging piles fromi
toh
into one pile and fromh + 1
toj
intok - 1
piles. -
Final Calculation: After considering
k
piles, we calculatef[i][j][1]
if we are merging into one pile from the current rangei
toj
. The cost here is the minimal cost of merging intoK
piles plus the sum of all stones in the current range.
The main algorithmic concepts used in this solution are dynamic programming for breaking down the problem into overlapping subproblems and calculating their minimal costs, and the prefix sum technique for fast range sum queries. The use of a 3D array allows keeping track of costs for different numbers of resulting piles in the subranges.
The final answer is found in f[1][n][1]
which gives the minimum cost to merge all piles from 1
to n
into one pile.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's use a small example to illustrate the solution approach:
Suppose we have n = 5
piles of stones, arranged in a row and the piles contain {3, 2, 4, 1, 2}
stones respectively. We can only merge k = 3
consecutive piles at a time.
Following the solution approach:
-
Initialization: We check
(n - 1) % (k - 1) = (5 - 1) % (3 - 1) = 0
, so we can proceed. -
Prefix Sum Array: We prepare the prefix sum array
s
, which will be{0, 3, 5, 9, 10, 12}
wheres[i] = s[i-1] + stones[i-1]
. -
DP Table: We initialize a 3D DP array
f
with dimensions[n+1][n+1][k+1]
. We'll setf[i][i][1]
to0
fori
from1
to5
. -
Subproblem Solutions: We iterate through subranges of length
l = 2
to5
. For example:- When
l = 2
, our subranges are(1, 2)
,(2, 3)
,(3, 4)
, and(4, 5)
. We're going to calculate the minimum cost to turn each size-2 subrange into a single pile. - We continue with
l = 3
,l = 4
, and finallyl = 5
, which is our overall problem.
- When
-
Transition: We then iterate through all subranges and potential merge points to update our DP table. For example, looking at the subrange
(1, 3)
, we'd calculate the cost of merging pile1
into one pile and piles2-3
into one pile and add these costs together. -
Final Calculation: Every time we look at merging into a single pile (
k = 1
), we include the cost of the stones. For the case of our subrange(1, 3)
, after finding the minimum merge cost intok = 3
piles, we add the prefix sum of piles1
to3
, which iss[3] - s[0] = 9 - 0 = 9
.
Assuming we fill out the DP table with all the correct values through our iteration, we finally look at f[1][5][1]
for our answer.
Let's calculate step-by-step for this example:
- For
l = 2
, we just merge the neighboring piles. The costs aref[1][2][1] = 5
,f[2][3][1] = 6
,f[3][4][1] = 5
, andf[4][5][1] = 3
. - For
l = 3
, we have three possible merges for piles(1, 3)
,(2, 4)
, and(3, 5)
. We consider the cost forl = 2
cases we calculated and the single piles. For(1, 3)
, since we must merge 3 piles at once, the cost is the sum of piles1
to3
, sof[1][3][1] = 9
. - We continue this way until
l = 5
. Our final merge for(1, 5)
must consider the cost of merge into3
piles (k = 3
) plus the sum of stones from pile1
to5
, which isf[1][3][1] + f[4][5][1] + (s[5] - s[0]) = 9 + 3 + 12 = 24
.
Thus, the result is f[1][5][1] = 24
, which means the minimal cost to merge all piles from 1
to 5
into one pile is 24
.
Solution Implementation
1from itertools import accumulate
2from math import inf
3
4class Solution:
5 def mergeStones(self, stones: List[int], K: int) -> int:
6 # Calculate the total number of stones.
7 num_stones = len(stones)
8
9 # If we cannot converge to a single pile with given K, return -1.
10 if (num_stones - 1) % (K - 1):
11 return -1
12
13 # Calculate the prefix sum of the stones array for quick range sum calculation.
14 prefix_sum = list(accumulate(stones, initial=0))
15
16 # Initialize the dynamic programming table with infinity.
17 dp = [[[inf] * (K + 1) for _ in range(num_stones + 1)] for _ in range(num_stones + 1)]
18
19 # A single stone pile has 0 cost to merge.
20 for i in range(1, num_stones + 1):
21 dp[i][i][1] = 0
22
23 # Iterate over all possible lengths of the subarray of stones (from 2 to num_stones).
24 for length in range(2, num_stones + 1):
25 for i in range(1, num_stones - length + 2):
26 j = i + length - 1 # The end index of the subarray
27
28 # Iterate over all possible numbers of piles K.
29 for k in range(1, K + 1):
30
31 # Split the subarray into two parts and add the cost of merging them.
32 for h in range(i, j):
33 dp[i][j][k] = min(dp[i][j][k], dp[i][h][1] + dp[h + 1][j][k - 1])
34
35 # If we can form a single pile, calculate the cost including merging the last pile.
36 if k == 1:
37 dp[i][j][1] = dp[i][j][K] + prefix_sum[j] - prefix_sum[i - 1]
38
39 # Return the minimum cost to merge the entire array into one pile.
40 return dp[1][num_stones][1]
41
1class Solution {
2 public int mergeStones(int[] stones, int K) {
3 int stoneCount = stones.length;
4
5 // If it's not possible to merge to one pile, return -1
6 if ((stoneCount - 1) % (K - 1) != 0) {
7 return -1;
8 }
9
10 // Prefix sums of stones array for calculating subarray sums
11 int[] prefixSums = new int[stoneCount + 1];
12 for (int i = 1; i <= stoneCount; ++i) {
13 prefixSums[i] = prefixSums[i - 1] + stones[i - 1];
14 }
15
16 // Initialize DP table with infinity values except for the base case: f[i][i][1] = 0
17 final int infinity = 1 << 20;
18 int[][][] dpTable = new int[stoneCount + 1][stoneCount + 1][K + 1];
19 for (int[][] secondDimension : dpTable) {
20 for (int[] thirdDimension : secondDimension) {
21 Arrays.fill(thirdDimension, infinity);
22 }
23 }
24 for (int i = 1; i <= stoneCount; ++i) {
25 dpTable[i][i][1] = 0;
26 }
27
28 // Dynamic programming to find minimal cost
29 for (int length = 2; length <= stoneCount; ++length) {
30 for (int i = 1; i + length - 1 <= stoneCount; ++i) {
31 int j = i + length - 1;
32 for (int piles = 1; piles <= K; ++piles) {
33 // Calculate minimum cost for merging stones into 'piles' piles
34 for (int mid = i; mid < j; ++mid) {
35 dpTable[i][j][piles] = Math.min(dpTable[i][j][piles],
36 dpTable[i][mid][1] + dpTable[mid + 1][j][piles - 1]);
37 }
38 }
39 // Merge K piles into 1 pile incurs additional cost which is the sum of stones[i...j]
40 dpTable[i][j][1] = dpTable[i][j][K] + prefixSums[j] - prefixSums[i - 1];
41 }
42 }
43 // Return minimal cost to merge all stones into 1 pile
44 return dpTable[1][stoneCount][1];
45 }
46}
47
1class Solution {
2public:
3 int mergeStones(vector<int>& stones, int K) {
4 int n = stones.size();
5
6 // Check if it's possible to merge the stones into a single pile
7 if ((n - 1) % (K - 1) != 0) {
8 return -1;
9 }
10
11 // Prefix sums array to calculate the sum of stones between two indexes efficiently
12 vector<int> prefixSums(n + 1, 0);
13 for (int i = 1; i <= n; ++i) {
14 prefixSums[i] = prefixSums[i - 1] + stones[i - 1];
15 }
16
17 // Dynamic programming table where f[i][j][k] represents the minimum cost to merge
18 // stones[i] to stones[j] into k piles
19 vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(n + 1, vector<int>(K + 1, INT_MAX)));
20
21 // Base case: cost of a single stone (itself) as a pile is 0
22 for (int i = 1; i <= n; ++i) {
23 dp[i][i][1] = 0;
24 }
25
26 // Fill in dp table using bottom-up dynamic programming approach
27 for (int l = 2; l <= n; ++l) { // length of the range
28 for (int i = 1; i + l - 1 <= n; ++i) {
29 int j = i + l - 1;
30 for (int k = 2; k <= K; ++k) { // number of piles
31 for (int mid = i; mid < j; mid += K - 1) { // possible split point, ensuring mergeablility
32 dp[i][j][k] = min(dp[i][j][k], dp[i][mid][1] + dp[mid + 1][j][k - 1]);
33 }
34 }
35 // Cost to merge into 1 pile is the cost to make K piles plus the total sum of the stones
36 if (dp[i][j][K] < INT_MAX) {
37 dp[i][j][1] = dp[i][j][K] + prefixSums[j] - prefixSums[i - 1];
38 }
39 }
40 }
41
42 // Final answer: the cost to merge the whole array into one pile
43 return dp[1][n][1];
44 }
45};
46
1// Given an array of stones, returns the minimum cost to merge all stones into one pile
2function mergeStones(stones: number[], K: number): number {
3 let n: number = stones.length;
4
5 // Check if it's possible to merge the stones into a single pile
6 if ((n - 1) % (K - 1) !== 0) {
7 return -1;
8 }
9
10 // Prefix sums array to calculate the sum of stones between two indices efficiently
11 let prefixSums: number[] = new Array(n + 1).fill(0);
12 for (let i = 1; i <= n; ++i) {
13 prefixSums[i] = prefixSums[i - 1] + stones[i - 1];
14 }
15
16 // Dynamic programming table where dp[i][j][k] represents the minimum cost to merge
17 // stones from index i to j into k piles
18 let dp: number[][][] = Array.from({ length: n + 1 }, () =>
19 Array.from({ length: n + 1 }, () => new Array(K + 1).fill(Number.MAX_SAFE_INTEGER))
20 );
21
22 // Base case: cost of a single stone (itself) as one pile is 0
23 for (let i = 1; i <= n; ++i) {
24 dp[i][i][1] = 0;
25 }
26
27 // Fill in the dp table using a bottom-up dynamic programming approach
28 for (let length = 2; length <= n; ++length) {
29 for (let i = 1; i + length - 1 <= n; ++i) {
30 let j = i + length - 1;
31 for (let piles = 2; piles <= K; ++piles) {
32 for (let mid = i; mid < j; mid += K - 1) {
33 dp[i][j][piles] = Math.min(dp[i][j][piles], dp[i][mid][1] + dp[mid + 1][j][piles - 1]);
34 }
35 }
36 // Cost to merge into one pile is the cost to make K piles plus the total sum of the stones
37 if (dp[i][j][K] < Number.MAX_SAFE_INTEGER) {
38 dp[i][j][1] = dp[i][j][K] + prefixSums[j] - prefixSums[i - 1];
39 }
40 }
41 }
42
43 // The final answer is the cost to merge the entire array into one pile
44 return dp[1][n][1];
45}
46
Time and Space Complexity
The given Python code is designed to solve a problem on merging stones with certain constraints. Here's the analysis of the time complexity and space complexity of the code:
Time Complexity
The time complexity is influenced by several nested loops and the independent computation performed within them. Here's a breakdown:
-
The first loop initializes the
f
list with a single loop running forn
, resulting inO(n)
complexity. -
Then, there's a triple-nested loop structure where:
- The outermost loop runs for
n
times, indicating the different lengthsl
that the subproblems can take. - The second loop also runs up to
n
times, designating the starting pointi
of a subproblem. - The third loop iterates
K
times, which corresponds to the number of piles to merge. - Inside the third loop, there is an additional loop running for
j-i
times, which in the worst case isO(n)
.
- The outermost loop runs for
The innermost computation f[i][j][k] = min(f[i][j][k], f[i][h][1] + f[h + 1][j][k - 1])
happens in constant time O(1)
, since it's just a minimization of pre-calculated values and arithmetic operations.
Combining all these factors, the resulting time complexity is O(n^3 * K * n) = O(n^4 * K)
.
Space Complexity
The space complexity is influenced by the storage requirements of the f
list, which is a 3D list of dimensions (n + 1) x (n + 1) x (K + 1)
. This results in a space complexity of O(n^2 * K)
.
There are additional variables and a prefix sum array s
, but these have significantly lower space costs O(n)
compared to the f
list, so they do not affect the overall space complexity. Thus, the dominating term remains O(n^2 * K)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Consider the classic dynamic programming of longest increasing subsequence:
Find the length of the longest subsequence of a given sequence such that all elements of the subsequence are sorted in increasing order.
For example, the length of LIS for [50, 3, 10, 7, 40, 80]
is 4
and LIS is
[3, 7, 40, 80]
.
What is the recurrence relation?
Recommended Readings
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Prefix Sum The prefix sum is an incredibly powerful and straightforward technique Its primary goal is to allow for constant time range sum queries on an array What is Prefix Sum The prefix sum of an array at index i is the sum of all numbers from index 0 to i By
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Want a Structured Path to Master System Design Too? Donāt Miss This!