# 1000. Minimum Cost to Merge Stones

There are `N` piles of stones arranged in a row.  The `i`-th pile has `stones[i]` stones.

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`

这道题给了我们N堆石头，每堆石头有不同的个数，说每次可以合并K堆石头，合并堆的花费就是石头的个数，然后问如何合并，才能使总花费最小。然后给了一些例子，通过观察例子，可以发现，并不是所有的输入都能成功合成一堆，比如例子2，无论先和并哪三堆，最终都会剩下两堆，从而无法进一步合并，因为 K=3，每次至少需要合并三堆。我们当然希望能在开始合并之前就能知道最终是否能成功合并为一堆，而不是算到最后了才发现白忙了一场，所以要来分析一下，什么时候才能最终合并为一堆。再来看看例子2，每次要将三堆合并为一堆，那么就是减少了两堆，而要使得最终能够剩下一堆，其他的都要合并调，假设原来共有n堆，只能剩下一堆，就是说 n-1 堆都要减掉，而每次只能减少 k-1 堆，所以只要 n-1 能够整除 k-1即可，即 (n-1)%(k-1) == 0 成立，这样就可以提前判断了。

`dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j]); -> (i <= t < j)`

`dp[i][j] += sums[j + 1] - sums[i]; -> if ((j - i) % (K - 1) == 0)`

``````class Solution {
public:
int mergeStones(vector<int>& stones, int K) {
int n = stones.size();
if ((n - 1) % (K - 1) != 0) return -1;
vector<int> sums(n + 1);
vector<vector<int>> dp(n, vector<int>(n));
for (int i = 1; i < n + 1; ++i) {
sums[i] = sums[i - 1] + stones[i - 1];
}
for (int len = K; len <= n; ++len) {
for (int i = 0; i + len <= n; ++i) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int t = i; t < j; t += K - 1) {
dp[i][j] = min(dp[i][j], dp[i][t] + dp[t + 1][j]);
}
if ((j - i) % (K - 1) == 0) {
dp[i][j] += sums[j + 1] - sums[i];
}
}
}
return dp[0][n - 1];
}
};
``````

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1000

Burst Balloons

Remove Boxes

Cherry Pickup

https://leetcode.com/problems/minimum-cost-to-merge-stones/

https://leetcode.com/problems/minimum-cost-to-merge-stones/discuss/247567/JavaC%2B%2BPython-DP

LeetCode All in One 题目讲解汇总(持续更新中…)

 微信打赏 Venmo 打赏
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，试运营期间前五十位可享受半价优惠～）

×

Help us with donation