hardDynamic Programming 2DPure DSA~45 min
Minimum Cost to Merge Stone Piles
Stone piles sit in a row. In one move you merge exactly K consecutive piles into one, paying the sum of those piles. Merge everything into a single pile at the least total cost.
Problem
Given an array stones where stones[i] is the count in the i-th pile and an integer k, you may merge exactly k consecutive piles into one pile in each move, at a cost equal to the total stones in those k piles. Return the minimum total cost to merge all piles into one, or -1 if it is impossible.
Input
An integer array stones of length n and an integer k.
Output
An integer: minimum total merge cost, or -1 if impossible.
Constraints
- 1 <= stones.length <= 30
- 2 <= k <= 30
- 1 <= stones[i] <= 100
Examples
Example 1
Input
stones = [3,2,4,1], k = 2
Output
20
Merge to one pile via pairwise merges costing 20 total.
Example 2
Input
stones = [3,5,1,2,6], k = 3
Output
25
Merge [5,1,2]→8 then [3,8,6]→17, total 25.