Minimum Cost to Merge Stones

Hard30–35 min

Topics

Dynamic ProgrammingInterval DP

Companies

GoogleBloombergAmazon

A row of stone piles is given, along with a group size `k`. Every move fuses exactly `k` piles standing next to each other into a single pile, paying a cost equal to their combined weight; the goal is to keep merging until one pile remains, at the lowest total cost — or to recognize that ending on exactly one pile is impossible for this `n` and `k`, and report `-1`. Reachability comes first: each merge trades `k` piles for `1`, shrinking the pile count by `k−1` every time, so the only counts ever reachable from `n` are `n, n−(k−1), n−2(k−1), …` — landing on 1 requires `(n−1)` to be a multiple of `(k−1)`, otherwise no sequence of moves ever finishes. Given that a solution exists, the same reachability rule applies to every sub-range too: split a range into two pieces at any point spaced `(k−1)` piles apart, solve each piece as its own smaller version of the problem, and whenever a range's own pile count can collapse to one, pay for that final merge by adding the range's total weight. Filling this in from short ranges up to the full array means every smaller answer a longer range needs has already been computed once.

Test Case 1:

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

Output:20

Explanation:Merge (4,1) for 5, then (3,2) for 5, then merge those two results (3+2=5 and 4+1=5) for 10 — 5+5+10 = 20 is one way to reach the minimum; the DP finds this without trying every merge order by hand.

Test Case 2:

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

Output:-1

Explanation:Every merge fuses exactly 3 piles into 1, so the pile count only ever drops by steps of 2 (k−1). Starting from 4 piles, the reachable counts are 4, 2 — never 1. No sequence of moves can finish, so the answer is -1.

Test Case 3:

Input:stones = [1], k = 3

Output:0

Explanation:Already down to a single pile before any move is needed — nothing to merge, cost 0, regardless of what k is.

Constraints

◆1 ≤ stones.length ≤ 8
◆2 ≤ k ≤ stones.length
◆1 ≤ stones[i] ≤ 100

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

Look at a contiguous range of piles as its own smaller version of the same problem: pick where to split the range into two pieces, solve each piece independently and add their costs, and try every split point spaced (k−1) piles apart (any other spacing could never line up with "merge exactly k at a time"). Once a range's own merges are done, check whether the piles now sitting in it can be fused into one final pile in a single k-way move — that's only possible when the range's pile count minus one is itself a multiple of (k−1), which is exactly the same reachability rule that decides whether the whole problem is solvable at all. Recursing this way is correct, but the same range gets re-split and re-solved from scratch every time a different outer split happens to pass through it.

TimeO(exponential)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] stones;
    private int k;
    private int[] prefix;

    public int mergeStones(int[] stones, int k) {
        this.stones = stones;
        this.k = k;
        int n = stones.length;
        if ((n - 1) % (k - 1) != 0) return -1;
        prefix = new int[n + 1];
        for (int i = 0; i < n; i++) prefix[i + 1] = prefix[i] + stones[i];
        return solve(0, n - 1);
    }

    private int solve(int i, int j) {
        if (j - i + 1 < k) return 0;
        int best = Integer.MAX_VALUE;
        for (int m = i; m < j; m += (k - 1)) {
            int cost = solve(i, m) + solve(m + 1, j);
            if (cost < best) best = cost;
        }
        if ((j - i) % (k - 1) == 0) {
            best += prefix[j + 1] - prefix[i];
        }
        return best;
    }
}

Optimal — Bottom-Up Interval DP

Optimal

Build the same recursion bottom-up instead of top-down, filling dp[i][j] — the minimum cost to do every merge that's possible within piles i..j — for shorter ranges before longer ones, so every dp[i][m] and dp[m+1][j] a split needs is already sitting in the table. Each entry still tries every split point (k−1) apart and still adds the range's full stone sum whenever that range can collapse to one pile, exactly like the recursive version — the only difference is that each range's answer gets computed exactly once and reused by every later range that needs it, turning the repeated work into a table lookup.

TimeO(n³ / k)

SpaceO(n²)