586. Minimum Cost to Merge Stones
There are n piles of stones lined up in a row; stones[i] is the number of stones in the i-th pile.
A single move takes exactly k consecutive piles and merges them into one new pile that sits in their place. Each merge costs the combined stone count of the piles involved.
Given the array stones and the integer k, return the minimum total cost to merge everything into one single pile. If no sequence of moves can ever reach one pile, return -1.
Example 1:
Input: stones = [3,2,4,1], k = 2
Output: 20
Explanation: Merge [3,2] for cost 5 → piles [5,4,1]. Merge [4,1] for cost 5 → piles [5,5]. Merge [5,5] for cost 10 → one pile. Total 5 + 5 + 10 = 20, and no ordering does better.
Example 2:
Input: stones = [3,2,4,1], k = 3
Output: -1
Explanation: Every move removes exactly k − 1 = 2 piles. Starting from 4 piles you can only reach 2 piles, never 1 — so the target is impossible.
Example 3:
Input: stones = [3,5,1,2,6], k = 3
Output: 25
Explanation: Merge [5,1,2] for cost 8 → piles [3,8,6]. Merge [3,8,6] for cost 17 → one pile. Total 25.
Constraints:
- 1 ≤ stones.length ≤ 30
- 2 ≤ k ≤ 30
- 1 ≤ stones[i] ≤ 100
Hints:
Every move shrinks the number of piles by exactly k − 1. So reaching a single pile from n piles is possible only when (n − 1) is a multiple of (k − 1) — check that before doing any work.
Merges never reorder anything: any intermediate pile is the fusion of a consecutive block of the original array. That screams interval DP — solve every contiguous range and combine.
Let dp[i][j] be the cheapest cost to shrink stones[i..j] down to as few piles as that range allows. Split at m so the left part collapses to exactly one pile — m only needs to jump in steps of k − 1 — and when (j − i) is a multiple of (k − 1), pay sum(i..j) once more to fuse the final k piles into one.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: stones = [3,2,4,1], k = 2
Expected output: 20