Minimum Cost to Merge Stones Hard 0 attempts
LeetCode ↗

Minimum Cost to Merge Stones

Hard Dynamic ProgrammingMemoization LeetCode

You have a row of stone piles and a number k. In one move, you may merge exactly k piles that sit next to each other into a single pile, and that move costs the sum of the stones involved. Return the minimum total cost to merge all piles into exactly one pile, or -1 if this is impossible.

Input Format
Implement mergeStones(stones, k). Inputs below show JavaScript function arguments; there is no stdin parsing.
Output Format
Return the result described in the statement.

Sample Input and Output

Example 1 · Run Sample

Input
stones = [3,2,4,1]
k = 2
Output
20

Example 2

Input
stones = [3,2,4,1]
k = 3
Output
-1
Constraints
  • 1 <= stones.length <= 30
  • 1 <= stones[i] <= 100
  • 2 <= k <= 30
Test Cases (2)
Case 1
Args: [[3,2,4,1],2] Expected: 20
Case 2
Args: [[3,2,4,1],3] Expected: -1
Topics
Dynamic ProgrammingMemoization

Interval DP

javascript
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