1547. Minimum Cost to Cut a Stick

题目信息

题号:

1547

难度:

Hard

主题:

区间动态规划、排序、切割

原题:

LeetCode 1547

重点:

每次切割成本等于当时所在木棍段的长度;可以任意安排切割顺序,求完成全部指定切口的最小总成本

题目重述

有一根长度为 n 的木棍,覆盖坐标 [0,n]。数组 cuts 给出必须切割的内部位置,所有位置互不相同。

每次在某个尚未切开的木棍段中执行一个指定切割,成本等于该段当前长度。请安排切割顺序,使完成全部切割的总成本最小,并返回该最小值。

2 <= n <= 10^6,1 <= cuts.length <= 100,每个切口严格位于 0 与 n 之间。

自建示例

先切靠近中间的位置可以降低后续成本:

输入:n = 7, cuts = [1,3]
输出:10
解释:先在 3 处切割成本 7,再在左段的 1 处切割成本 3,总计 10。

只有一个切口时成本就是整根木棍长度:

输入:n = 2, cuts = [1]
输出:2
解释:第一次也是唯一一次切割发生在长度为 2 的木棍上。