#### 原题说明

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:**

#### 解题思路

**动态规划：**`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]`

**状态转移方程:**

`k >= 2`

`dp[i][j][k] = min{dp[i][m][1] + dp[m+1][j][k-1]}`

for all`i <= m < j`

`k == 1`

`dp[i][j][1] = dp[i][j][K] + sum of (stones[i] to stones[j])`

#### 示例代码 (cpp)

1 | class Solution { |

#### 复杂度分析

时间复杂度: `O(n^3)`

空间复杂度: `O(n^2 * K)`

#### 归纳总结

这道题还有更加优化的动态规划解法，但是思路不是非常直接，面试时也不太会要求掌握，同学们如果希望看到讲解，可以留言告诉我们。

我们在**Youtube**上更新了视频讲解，欢迎关注！