Problem

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.

Examples

Example 1

1
2
3
4
5
6
7

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

1
2
3

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

1
2
3
4
5
6

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.length
  • 1 <= n <= 30
  • 1 <= stones[i] <= 100
  • 2 <= k <= 30

Solution

Method 1 – Dynamic Programming with Prefix Sum

Intuition

We use DP to track the minimum cost to merge subarrays of stones into a certain number of piles. We use prefix sums to quickly calculate the cost of merging. The key is to only merge when the number of piles is reducible to 1 by repeatedly merging k piles.

Approach

  1. If (n-1) % (k-1) != 0, return -1 (impossible to merge into one pile).
  2. Compute prefix sums for quick range sum queries.
  3. Use a 3D DP array: dp[i][j][m] is the min cost to merge stones[i..j] into m piles.
  4. Base case: dp[i][i][1] = 0.
  5. For each length, for each i, j, for each m:
    • For m > 1, try all possible splits and update dp[i][j][m].
    • For m == 1, merge k piles and add the cost.
  6. The answer is dp[0][n-1][1].

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

class Solution {
public:
    int mergeStones(vector<int>& stones, int k) {
        int n = stones.size();
        if ((n-1) % (k-1)) return -1;
        vector<int> prefix(n+1);
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + stones[i];
        vector<vector<vector<int>>> dp(n, vector<vector<int>>(n, vector<int>(k+1, 1e9)));
        for (int i = 0; i < n; ++i) dp[i][i][1] = 0;
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i+len-1 < n; ++i) {
                int j = i+len-1;
                for (int m = 2; m <= k; ++m) {
                    for (int mid = i; mid < j; mid += k-1) {
                        dp[i][j][m] = min(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1]);
                    }
                }
                if ((len-1) % (k-1) == 0) {
                    dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i];
                }
            }
        }
        return dp[0][n-1][1];
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

func mergeStones(stones []int, k int) int {
    n := len(stones)
    if (n-1)%(k-1) != 0 {
        return -1
    }
    prefix := make([]int, n+1)
    for i := 0; i < n; i++ {
        prefix[i+1] = prefix[i] + stones[i]
    }
    dp := make([][][]int, n)
    for i := range dp {
        dp[i] = make([][]int, n)
        for j := range dp[i] {
            dp[i][j] = make([]int, k+1)
            for m := range dp[i][j] {
                dp[i][j][m] = 1<<30
            }
        }
    }
    for i := 0; i < n; i++ {
        dp[i][i][1] = 0
    }
    for l := 2; l <= n; l++ {
        for i := 0; i+l-1 < n; i++ {
            j := i+l-1
            for m := 2; m <= k; m++ {
                for mid := i; mid < j; mid += k-1 {
                    if dp[i][j][m] > dp[i][mid][1]+dp[mid+1][j][m-1] {
                        dp[i][j][m] = dp[i][mid][1]+dp[mid+1][j][m-1]
                    }
                }
            }
            if (l-1)%(k-1) == 0 {
                dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i]
            }
        }
    }
    return dp[0][n-1][1]
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

class Solution {
    public int mergeStones(int[] stones, int k) {
        int n = stones.length;
        if ((n-1) % (k-1) != 0) return -1;
        int[] prefix = new int[n+1];
        for (int i = 0; i < n; ++i) prefix[i+1] = prefix[i] + stones[i];
        int[][][] dp = new int[n][n][k+1];
        for (int[][] arr : dp)
            for (int[] a : arr)
                Arrays.fill(a, Integer.MAX_VALUE/2);
        for (int i = 0; i < n; ++i) dp[i][i][1] = 0;
        for (int len = 2; len <= n; ++len) {
            for (int i = 0; i+len-1 < n; ++i) {
                int j = i+len-1;
                for (int m = 2; m <= k; ++m) {
                    for (int mid = i; mid < j; mid += k-1) {
                        dp[i][j][m] = Math.min(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1]);
                    }
                }
                if ((len-1) % (k-1) == 0) {
                    dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i];
                }
            }
        }
        return dp[0][n-1][1];
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    fun mergeStones(stones: IntArray, k: Int): Int {
        val n = stones.size
        if ((n-1) % (k-1) != 0) return -1
        val prefix = IntArray(n+1)
        for (i in stones.indices) prefix[i+1] = prefix[i] + stones[i]
        val dp = Array(n) { Array(n) { IntArray(k+1) { 1_000_000_000 } } }
        for (i in 0 until n) dp[i][i][1] = 0
        for (len in 2..n) {
            for (i in 0..n-len) {
                val j = i+len-1
                for (m in 2..k) {
                    for (mid in i until j step k-1) {
                        dp[i][j][m] = minOf(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1])
                    }
                }
                if ((len-1) % (k-1) == 0) {
                    dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i]
                }
            }
        }
        return dp[0][n-1][1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20

class Solution:
    def mergeStones(self, stones: list[int], k: int) -> int:
        n = len(stones)
        if (n-1) % (k-1):
            return -1
        prefix = [0]*(n+1)
        for i in range(n):
            prefix[i+1] = prefix[i] + stones[i]
        dp = [[[float('inf')] * (k+1) for _ in range(n)] for _ in range(n)]
        for i in range(n):
            dp[i][i][1] = 0
        for l in range(2, n+1):
            for i in range(n-l+1):
                j = i+l-1
                for m in range(2, k+1):
                    for mid in range(i, j, k-1):
                        dp[i][j][m] = min(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1])
                if (l-1) % (k-1) == 0:
                    dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i]
        return dp[0][n-1][1]
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

impl Solution {
    pub fn merge_stones(stones: Vec<i32>, k: i32) -> i32 {
        let n = stones.len();
        if (n-1) % (k-1) != 0 { return -1; }
        let mut prefix = vec![0; n+1];
        for i in 0..n { prefix[i+1] = prefix[i] + stones[i]; }
        let mut dp = vec![vec![vec![i32::MAX/2; k as usize+1]; n]; n];
        for i in 0..n { dp[i][i][1] = 0; }
        for len in 2..=n {
            for i in 0..=n-len {
                let j = i+len-1;
                for m in 2..=k as usize {
                    for mid in (i..j).step_by((k-1) as usize) {
                        dp[i][j][m] = dp[i][j][m].min(dp[i][mid][1] + dp[mid+1][j][m-1]);
                    }
                }
                if (len-1) % (k-1) == 0 {
                    dp[i][j][1] = dp[i][j][k as usize] + prefix[j+1] - prefix[i];
                }
            }
        }
        dp[0][n-1][1]
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

class Solution {
    mergeStones(stones: number[], k: number): number {
        const n = stones.length
        if ((n-1) % (k-1) !== 0) return -1
        const prefix = Array(n+1).fill(0)
        for (let i = 0; i < n; ++i) prefix[i+1] = prefix[i] + stones[i]
        const dp = Array.from({length: n}, () => Array.from({length: n}, () => Array(k+1).fill(Infinity)))
        for (let i = 0; i < n; ++i) dp[i][i][1] = 0
        for (let len = 2; len <= n; ++len) {
            for (let i = 0; i+len-1 < n; ++i) {
                const j = i+len-1
                for (let m = 2; m <= k; ++m) {
                    for (let mid = i; mid < j; mid += k-1) {
                        dp[i][j][m] = Math.min(dp[i][j][m], dp[i][mid][1] + dp[mid+1][j][m-1])
                    }
                }
                if ((len-1) % (k-1) === 0) {
                    dp[i][j][1] = dp[i][j][k] + prefix[j+1] - prefix[i]
                }
            }
        }
        return dp[0][n-1][1]
    }
}

Complexity

  • ⏰ Time complexity: O(n^3/k) — Triple loop for DP, step by k-1.
  • 🧺 Space complexity: O(n^2k) — For the DP array.