Minimum cost to merge stones

Array Dynamic Programming Prefix Sum

45.6% acceptance

Feb 25, 2026

2628

116

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn merge_stones(stones: Vec<i32>, k: i32) -> i32 {
    let n = stones.len();
    let k = k as usize;
    if (n - 1) % (k - 1) != 0 { return -1; }
    let mut prefix = vec![0i32; n + 1];
    for i in 0..n { prefix[i+1] = prefix[i] + stones[i]; }
    let mut dp = vec![vec![0i32; n]; n];
    for len in k..=n {
      for i in 0..=n-len {
        let j = i + len - 1;
        dp[i][j] = i32::MAX;
        let mut m = i;
        while m < j {
          if dp[i][m] != i32::MAX && dp[m+1][j] != i32::MAX {
            dp[i][j] = dp[i][j].min(dp[i][m] + dp[m+1][j]);
          }
          m += k - 1;
        }
        if (j - i) % (k - 1) == 0 {
          dp[i][j] += prefix[j+1] - prefix[i];
        }
      }
    }
    dp[0][n-1]
  }
}