LeetCode 1547:切棍子的最小成本

编程入门 行业动态 更新时间:2024-10-26 14:34:25

LeetCode 1547:切<a href=https://www.elefans.com/category/jswz/34/1706668.html style=棍子的最小成本"/>

LeetCode 1547:切棍子的最小成本

文章目录

    • 题目
    • 示例
      • 示例1
      • 示例2
    • 代码

题目

有一根长度为 n 个单位的木棍,棍上从 0 到 n 标记了若干位置。例如,长度为 6 的棍子可以标记如下:

给你一个整数数组 cuts ,其中 cuts[i] 表示你需要将棍子切开的位置。
你可以按顺序完成切割,也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度,切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍(这两根木棍的长度和就是切割前木棍的长度)。请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本 。

示例

示例1

输入:n = 7, cuts = [1,3,4,5]
输出:16
解释:
[1, 3, 4, 5] 的顺序切割的情况如下所示:

第一次切割长度为 7 的棍子,成本为 7 。第二次切割长度为 6 的棍子(即第一次切割得到的第二根棍子),第三次切割为长度 4 的棍子,最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。
而将切割顺序重新排列为 [3, 5, 1, 4] 后,

总成本 = 16(如示例图中 7 + 4 + 3 + 2 = 16)。

示例2

输入:n = 9, cuts = [5,6,1,4,2]
输出:22
解释:如果按给定的顺序切割,则总成本为 25 。总成本 <= 25 的切割顺序很多,例如,[4,6,5,2,1] 的总成本 = 22,是所有可能方案中成本最小的。

2 <= n <= 10^6
1 <= cuts.length <= min(n - 1, 100)
1 <= cuts[i] <= n - 1
cuts 数组中的所有整数都 互不相同

代码

思路:

  • 将木棍的两个端点(0和n)加到cuts数组中变为newCuts数组,并使其升序排列,dp[l][r]表示把这段木棍的第l到第r个切割点完成切割的最小成本(l和r为newCuts数组的下标)。
  • 每次都想把第i到第j个切割点的这段木棍(即区间内)切割为两份(每份内可能还有切割点需要切割),且成本最小。故可以逆过来,比如先dp得到每连续三个切割点切割为两份的最小成本,然后可以通过前者信息,dp计算每连续四个点切割为两份的最小成本…
  1. 当r=l+1,即两个相邻切割点,其本身区间内只有一段,故不需要切割,成本为0;
  2. 当r>l+1时,在(l,r)间取切割点k,即在k处切断,其切割的成本为区间长度newCuts[r] - newCuts[l];
  3. 故将区间内(即第l到第r个切割点完成切割)的最小成本转换方程为:dp[l][r] = min {dp[l][k]+dp[k][r]+cuts[r]-cuts[l]},其中k∈(l, r)开区间的整数。
class Solution {public int minCost(int n, int[] cuts) {int[] newCuts = new int[cuts.length + 2];newCuts[0] = 0;for(int i=0;i<cuts.length;i++){newCuts[i+1] = cuts[i];}newCuts[cuts.length + 1] = n;Arrays.sort(newCuts);int[][] dp = new int[newCuts.length][newCuts.length];//枚举区间,len表示区间长度for(int len=2;len<newCuts.length;len++){//枚举区间左端点for(int i=0;i+len<newCuts.length;i++){//j为区间右端点int j = i + len;dp[i][j] = Integer.MAX_VALUE;//枚举区间的分割点for(int k=i+1;k<j;k++){dp[i][j] = Math.min(dp[i][j],dp[i][k]+dp[k][j]+newCuts[j]-newCuts[i]);}}}return dp[0][newCuts.length-1];}
}

LeetCode 1547. 切棍子的最小成本

更多推荐

LeetCode 1547:切棍子的最小成本

本文发布于:2024-02-27 13:08:42,感谢您对本站的认可!
本文链接:https://www.elefans.com/category/jswz/34/1706666.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
本文标签:棍子   最小   成本   LeetCode

发布评论

评论列表 (有 0 条评论)
草根站长

>www.elefans.com

编程频道|电子爱好者 - 技术资讯及电子产品介绍!