LeetCode 1000. Minimum Cost to Merge Stones

时间:2022-12-26 00:33:05

原题链接在这里: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.

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

题解:

Each merge step, piles number decreased by K-1. Eventually there is only 1 pile. n - mergeTimes * (K-1) == 1. megeTimes = (n-1)/(K-1). If it is not divisable, then it could not merge into one pile, thus return -1.

Let dp[i][j] denotes minimum cost to merge [i, j] inclusively.

m = i, i+1, ... j-1. Let i to m be one pile, and m+1 to j to certain piles. dp[i][j] = min(dp[i][m] + dp[m+1][j]).

In order to make i to m as one pile, [i,m] inclusive length is multiple of K. m moves K-1 each step.

If [i, j] is multiple of K, then dp[i][j] could be merged into one pile. dp[i][j] += preSum[j+1] - preSum[i].

return dp[0][n-1], minimum cost to merge [0, n-1] inclusively.

Time Complexity: O(n^3/K).

Space: O(n^2).

AC Java:

 class Solution {
public int mergeStones(int[] stones, int K) {
int n = stones.length;
if((n-1)%(K-1) != 0){
return -1;
} int [] preSum = new int[n+1];
for(int i = 1; i<=n; i++){
preSum[i] = preSum[i-1] + stones[i-1];
} int [][] dp = new int[n][n];
for(int size = 2; size<=n; size++){
for(int i = 0; i<=n-size; i++){
int j = i+size-1;
dp[i][j] = Integer.MAX_VALUE; for(int m = i; m<j; m += K-1){
dp[i][j] = Math.min(dp[i][j], dp[i][m]+dp[m+1][j]);
} if((size-1) % (K-1) == 0){
dp[i][j] += preSum[j+1] - preSum[i];
}
}
} return dp[0][n-1];
}
}

类似Burst Balloons.

LeetCode 1000. Minimum Cost to Merge Stones的更多相关文章

  1. 1000&period; 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 ...

  2. &lbrack;LeetCode&rsqb; 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 ...

  3. &lbrack;Swift&rsqb;LeetCode1000&period; 合并石头的最低成本 &vert; 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 ...

  4. 动态规划-Minimum Cost to Merge Stones

    2019-07-07 15:48:46 问题描述: 问题求解: 最初看到这个问题的时候第一反应就是这个题目和打破气球的题目很类似. 但是我尝试了使用dp将问题直接转为直接合并到一个堆问题复杂度迅速提高 ...

  5. LeetCode 983&period; Minimum Cost For Tickets

    原题链接在这里:https://leetcode.com/problems/minimum-cost-for-tickets/ 题目: In a country popular for train t ...

  6. LeetCode 1130&period; Minimum Cost Tree From Leaf Values

    原题链接在这里:https://leetcode.com/problems/minimum-cost-tree-from-leaf-values/ 题目: Given an array arr of ...

  7. &lbrack;LeetCode&rsqb; 857&period; Minimum Cost to Hire K Workers 雇佣K名工人的最低成本

    There are N workers.  The i-th worker has a quality[i] and a minimum wage expectation wage[i]. Now w ...

  8. &lbrack;LeetCode&rsqb; 857&period; Minimum Cost to Hire K Workers 雇K个工人的最小花费

    There are N workers.  The i-th worker has a quality[i] and a minimum wage expectation wage[i]. Now w ...

  9. Leetcode之动态规划(DP)专题-详解983&period; 最低票价(Minimum Cost For Tickets)

    Leetcode之动态规划(DP)专题-983. 最低票价(Minimum Cost For Tickets) 在一个火车旅行很受欢迎的国度,你提前一年计划了一些火车旅行.在接下来的一年里,你要旅行的 ...

随机推荐

  1. 简单配置 nginx 反向代理

    # Nginx 域名反向代理配置# 安装nginx yum install nginx -y# 修改配置文件 进入配置文件目录 cd /etc/nginx/conf.d 新建配置文件以.conf结尾 ...

  2. Kanzi编程基础2 - Kanzi节点读取和属性设置

    UI设计师在Kanzi studio把Kanzi的节点做好后,就要编码读取这些节点并根据实际功能去控制刷新它. Kanzi读取节点的api发生过很多次变化,从2.7.2.8到3.0,每次变化都比较大, ...

  3. 清除div中内容

    $.ajax({            url: "SearchSN.aspx",            data: "SN=" + $("#txtS ...

  4. IntelliJ IDEA自用快捷键 转载

    最常用快捷键- 未分类 command Binding Description defeat - Ctrl+/ 代码提示 No - Ctrl+Alt+L 格式化代码   - Ctrl+B 快速打开光标 ...

  5. Cookie Manager

    https://github.com/Rob--W/cookie-manager 修改饼干获取VIP标识

  6. &lpar;转)Makefile介绍

    2. Makefile介绍 make命令执行时,需要一个Makefile文件,以告诉make命令需要怎么样的去编译和链接程序. 首先,我们用一个示例来说明Makefile的书写规则.以便给大家一个感性 ...

  7. htaccess跨域

    目的:为了加快访问速度,减轻主站压力,把静态资源放到独立的服务器上,使用独立的域名 问题:浏览器为安全考虑,实施同源策略:ip/域名和端口必须相同 解决办法: 1.httpd.conf中,开启apac ...

  8. BZOJ3874&colon;&lbrack;AHOI2014&amp&semi;JSOI2014&rsqb;宅男计划&lpar;爬山法&rpar;

    Description  [故事背景] 自从迷上了拼图,JYY就变成了个彻底的宅男.为了解决温饱问题,JYY 不得不依靠叫外卖来维持生计. [问题描述] 外卖店一共有N种食物,分别有1到N编号.第i种 ...

  9. Hastable和Dictionary以及ArrayList和(List,LinkedList,数组)的区别

    Hastable和Dictionary的区别:(键值对) 1:单线程程序中推荐使用 Dictionary, 有泛型优势, 且读取速度较快, 容量利用更充分. 2:多线程程序中推荐使用 Hashtabl ...

  10. hdu1056

    #include <cstdio> void main(){ double length; double l[300]; l[1] = 1.0/2; int i; for (i = 2;; ...