# leetcode 1000. Minimum Cost to Merge Stones 区间dp 归并

#### 题目

https://leetcode.com/problems/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.

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 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 .
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 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 .
The total cost was 25, and this is the minimum possible.

Note:

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

#### 源码

``````class Solution {
public:
vector<vector<vector<long>>> dp;
vector<int> pre;
int DK;
int mergeStones(vector<int>& stones, int K) {
DK = K;
dp.resize(stones.size()+1,vector<vector<long>>(stones.size()+1,vector<long>(K+1,INT_MAX)));
pre.resize(stones.size()+1,0);
for(int i = 0;i < stones.size();++i){
pre[i]=pre[i==0?0:i-1]+stones[i];
}
return calDp(0,stones.size()-1,1)==INT_MAX?-1:calDp(0,stones.size()-1,1);
}
long calDp(int st,int ed,int k){
if(dp[st][ed][k]!=INT_MAX)return dp[st][ed][k];
if(st==ed){
return dp[st][ed][k] = k==1?0:INT_MAX;
}
if((ed-st-k+1)%(DK-1)!=0){
return dp[st][ed][k] = INT_MAX;
}
if(k == 1){
return dp[st][ed] = calDp(st,ed,DK)+pre[ed]-(st==0?0:pre[st-1]);
}
for(int t = st;t < ed;t += (DK-1)){
dp[st][ed][k] = min(dp[st][ed][k],calDp(st,t,1)+calDp(t+1,ed,k-1));
}
return dp[st][ed][k];
}
};
``````