Formatted question description: https://leetcode.ca/all/1000.html

# 1000. Minimum Cost to Merge Stones (Hard)

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 = 2Output:20Explanation: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 = 3Output:-1Explanation: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 = 3Output:25Explanation: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`

**Related Topics**:

Dynamic Programming

**Similar Questions**:

## Solution 1. DP

```
// OJ: https://leetcode.com/problems/minimum-cost-to-merge-stones/
// Time: O(N^3 / K)
// Space: O(N^2)
// Ref: https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247567/JavaC%2B%2BPython-DP
class Solution {
public:
int mergeStones(vector<int>& stones, int K) {
int N = stones.size();
if ((N - 1) % (K - 1)) return -1;
vector<int> prefix(N + 1);
partial_sum(stones.begin(), stones.end(), prefix.begin() + 1);
vector<vector<int>> dp(N, vector<int>(N));
for (int m = K; m <= N; ++m) {
for (int i = 0; i + m <= N; ++i) {
int j = i + m - 1;
dp[i][j] = INT_MAX;
for (int mid = i; mid < j; mid += K - 1) {
dp[i][j] = min(dp[i][j], dp[i][mid] + dp[mid + 1][j]);
}
if ((j - i) % (K - 1) == 0) dp[i][j] += prefix[j + 1] - prefix[i];
}
}
return dp[0][N - 1];
}
};
```

Java

```
class Solution {
public int mergeStones(int[] stones, int K) {
int length = stones.length;
if (length == 1)
return 0;
if ((length - 1) % (K - 1) != 0)
return -1;
int[] prefixSum = new int[length];
prefixSum[0] = stones[0];
for (int i = 1; i < length; i++)
prefixSum[i] = prefixSum[i - 1] + stones[i];
int[][][] dp = new int[length][length][K];
for (int i = 0; i < length; i++) {
for (int j = 0; j < length; j++) {
for (int k = 0; k < K; k++)
dp[i][j][k] = Integer.MAX_VALUE;
}
}
for (int i = 0; i < length; i++)
dp[i][i][0] = 0;
for (int curLength = 2; curLength <= length; curLength++) {
int maxStart = length - curLength;
for (int i = 0; i <= maxStart; i++) {
int end = i + curLength - 1;
for (int j = 1; j < K; j++) {
for (int k = i; k < end; k += K - 1) {
dp[i][end][j] = Math.min(dp[i][end][j], dp[i][k][0] + dp[k + 1][end][j - 1]);
dp[i][end][0] = sum(prefixSum, i, end) + dp[i][end][j];
}
}
}
}
return dp[0][length - 1][0];
}
public int sum(int[] prefixSum, int start, int end) {
if (start == 0)
return prefixSum[end];
else
return prefixSum[end] - prefixSum[start - 1];
}
}
```