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`` 之间。 自建示例 -------- 先切靠近中间的位置可以降低后续成本: .. code-block:: text 输入:n = 7, cuts = [1,3] 输出:10 解释:先在 3 处切割成本 7,再在左段的 1 处切割成本 3,总计 10。 只有一个切口时成本就是整根木棍长度: .. code-block:: text 输入:n = 2, cuts = [1] 输出:2 解释:第一次也是唯一一次切割发生在长度为 2 的木棍上。