Minimum Cost to Merge Stones Hard 0 attempts
LeetCode ↗

Minimum Cost to Merge Stones

Hard Dynamic ProgrammingMemoization LeetCode

Given piles of stones and integer k, merge k consecutive piles at a time with cost equal to their total. Return minimum cost, or -1 if impossible.

Example: stones=[3,2,4,1], k=2 → Output: 20

Sample Input
—
Sample Output
—
Constraints
  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100
  • 2 <= k <= 30
Topics
Dynamic ProgrammingMemoization

Interval DP

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

Time: O(n³/k) | Space: O(n²)

Saved in this browser only. Private to you.

JavaScript