1547. 切棍子的最小成本

Difficulty
Hard
Tags
动态规划
URL
https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/
Star
有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：
notion imagenotion image
给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。
你可以按顺序完成切割，也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本 。
示例 1：
notion imagenotion image
输入：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）。
notion imagenotion image
示例 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 数组中的所有整数都 互不相同
通过次数4,741提交次数8,594

法 1 动态规划

思路
将木棍的两个端点（0和n）加到cuts数组中，
dp[i][j]表示把这段木棍的第i到j个点完成切割的最小成本,i和j都是cuts数组的下标。
如果j=i+1 则不需要切割，成本为0，这是边界； 
j>i+1时可以在i和j间取一点k，那么有dp[i][j]=min{dp[i][k]+dp[k][j]+cuts[j]-cuts[i]}，即在k处切断，这个切割的成本为cuts[j]-cuts[i] 所以有转移方程dp[i][j]=min{dp[i][k]+dp[k][j]+cuts[j]-cuts[i]} , i<k<j
题解
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        cuts = [0] + cuts + [n]

        cuts.sort()

        # dp[i][j]: 将cuts[i] cuts[j] 中间的段切开 的最小成本
        dp = [[float("inf")] * len(cuts) for _ in cuts]

        # 初始化
        # dp[i][i+1] = 0 中间不需要再切了
        # dp[i][i] = 0
        for i in range(0, len(dp)):
            dp[i][i] = 0
            if i < len(dp) - 1:
                dp[i][i+1] = 0

        # 状态转移
        for i in range(len(dp)-1, -1, -1):
            for j in range(i+2, len(dp), 1):
								# 枚举切割点
                for k in range(i+1, j):
                    dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j] + (cuts[j]-cuts[i]))


        return dp[0][-1]