Minimum Cost to Merge Stones
There are n piles of stones arranged in a row. The i^th 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.
Example 1
Input
stones = [3,2,4,1], k = 2Output
20The minimum cost is achieved by merging [3, 2] for 5, then [4, 1] for 5, then [5, 5] for 10, for a total cost of 20.
Example 2
Input
stones = [3,2,4,1], k = 3Output
-1After any merge operation, there are 2 piles left, and they cannot be merged with k = 3, so the task is impossible.
Constraints
- n == stones.length
- 1 <= n <= 30
- 1 <= stones[i] <= 100
- 2 <= k <= 30