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 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 个石堆,需要考虑从 t 开始,[i,t] 合并成一个石堆,[t+1,j] 合并成 k-1 个石堆,t 的步长为 K-1,边界条件为 i == j

源码

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][1] = 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];
    }
};

发表评论

电子邮件地址不会被公开。 必填项已用*标注