百度搜索引擎入口,江苏短视频seo搜索,河南热点新闻事件,网站调试文章目录1. 题目2. 解题1. 题目
有 N 堆石头排成一排#xff0c;第 i 堆中有 stones[i] 块石头。
每次移动#xff08;move#xff09;需要将连续的 K 堆石头合并为一堆#xff0c;而这个移动的成本为这 K 堆石头的总数。
找出把所有石头合并成一堆的最低成本。如果不可…
文章目录1. 题目2. 解题1. 题目
有 N 堆石头排成一排第 i 堆中有 stones[i] 块石头。
每次移动move需要将连续的 K 堆石头合并为一堆而这个移动的成本为这 K 堆石头的总数。
找出把所有石头合并成一堆的最低成本。如果不可能返回 -1 。
示例 1
输入stones [3,2,4,1], K 2
输出20
解释
从 [3, 2, 4, 1] 开始。
合并 [3, 2]成本为 5剩下 [5, 4, 1]。
合并 [4, 1]成本为 5剩下 [5, 5]。
合并 [5, 5]成本为 10剩下 [10]。
总成本 20这是可能的最小值。示例 2
输入stones [3,2,4,1], K 3
输出-1
解释任何合并操作后都会剩下 2 堆我们无法再进行合并。
所以这项任务是不可能完成的。.示例 3
输入stones [3,5,1,2,6], K 3
输出25
解释
从 [3, 5, 1, 2, 6] 开始。
合并 [5, 1, 2]成本为 8剩下 [3, 8, 6]。
合并 [3, 8, 6]成本为 17剩下 [17]。
总成本 25这是可能的最小值。提示
1 stones.length 30
2 K 30
1 stones[i] 100来源力扣LeetCode 链接https://leetcode-cn.com/problems/minimum-cost-to-merge-stones 著作权归领扣网络所有。商业转载请联系官方授权非商业转载请注明出处。 2. 解题
dp[i][j] 表示区间 [i, j] 尽量合并后的最小花费区间可能不能合并为1堆注意枚举区间中点 mid 时mid 增量 为 K-1
class Solution {
public:int mergeStones(vectorint stones, int K) {int n stones.size();if((n-1)%(K-1) ! 0) return -1;//不可能合并vectorvectorint dp(n1, vectorint(n1, 0));vectorint sum(n1, 0);for(int i 1; i n; i)sum[i] stones[i-1] sum[i-1];//前缀和for(int len 1; len n; len){ //区间长度for(int i 1; ilen n; i){ //左端点int j ilen;//右端点dp[i][j] INT_MAX;for(int mid i; mid j; mid K-1)//枚举中间分割点{ //注意mid不能, 而是 K-1 , 的话很可能左右区间不能合并dp初始为0得出的结果小dp[i][j] min(dp[i][j], dp[i][mid]dp[mid1][j]);}if(len%(K-1) 0)//如果区间能够合并加上区间石头数量dp[i][j] sum[j]-sum[i-1];}}return dp[1][n];}
};8 ms 8.4 MB C 我的CSDN博客地址 https://michael.blog.csdn.net/
长按或扫码关注我的公众号Michael阿明一起加油、一起学习进步
