#### 原题说明

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.

Find 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 = 2`
Output: `20`
Explanation:
We start with `[3, 2, 4, 1]`.
We merge `[3, 2]` for a cost of 5, and we are left with `[5, 4, 1]`.
We merge `[4, 1]` for a cost of 5, and we are left with `[5, 5]`.
We merge `[5, 5]` for a cost of 10, and we are left with `[10]`.
The total cost was `20`, and this is the minimum possible.

Example 2:

Input: `stones = [3,2,4,1], K = 3`
Output: `-1`
Explanation: After any merge operation, there are `2` piles left, and we can’t merge anymore. So the task is impossible.

Example 3:

Input: `stones = [3,5,1,2,6], K = 3`
Output: `25`
Explanation:
We start with `[3, 5, 1, 2, 6]`.
We merge `[5, 1, 2]` for a cost of 8, and we are left with `[3, 8, 6]`.
We merge `[3, 8, 6]` for a cost of 17, and we are left with `[17]`.
The total cost was 25, and this is the minimum possible.

Note:

• `1 <= stones.length <= 30`
• `2 <= K <= 30`
• `1 <= stones[i] <= 100`

#### 解题思路

`dp[i][j][k]` := 将`i``j`合并成`k`堆的最小cost

`dp[i][j][k] = 0 if i==j and k == 1 else inf`

`dp[0][n-1][1]`

1. `k >= 2`
`dp[i][j][k] = min{dp[i][m][1] + dp[m+1][j][k-1]}` for all `i <= m < j`
2. `k == 1`
`dp[i][j][1] = dp[i][j][K] + sum of (stones[i] to stones[j])`

#### 归纳总结

------ 关注公众号：猩猩的乐园 ------