棍子的最小成本"/>
leetcode 5486. 切棍子的最小成本
5486. 切棍子的最小成本
有一根长度为 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= [1,3,4,5];加了过后的数组变为 [0,1,3,4,5,7],首尾是用来计算中间部分的长度会用到。
- 接下来就是限制条件,之前的打气球没有啥限制条件。但是这道题有一个条件就是两个要裁剪的地方,中间如果没有要裁剪的地方,那么这样的两者之间的损耗是0.转换为程序语言就是 dp[i][i+1] = 0.
- 设置一个dp动态转移矩阵,dp[i][j]表示裁剪点i与裁剪点 j之间的损耗。
- 我们可以得到动态转移方程如下所示:
d p [ i ] [ j
更多推荐
leetcode 5486. 切棍子的最小成本
发布评论