跳转至

1547. 切棍子的最小成本

#python #leetcode #dp

题目描述

关联：https://leetcode.cn/problems/minimum-cost-to-cut-a-stick/description/

题目描述

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

statement

给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。

你可以按顺序完成切割，也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。

返回切棍子的 最小总成本 。

样例 1

e1

  • 输入：n = 7, cuts = [1,3,4,5]
  • 输出：16

解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：

e11

第一次切割长度为 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，是所有可能方案中成本最小的。

解题思路

本题仍然可以使用动态规划解决。使用二维数组 dp[i][j] 表示在 \(\text{cuts}_i\) 和 \(\text{cuts}_j\) 之间切割的最小成本。

首先选择切割点，在 \(\text{cuts}_i\) 和 \(\text{cuts}_j\) 之间选择一个点 \(\text{cuts}_k\)，其中 \(i < k < j\)。此时将棍子切割成两部分，分别计算两部分的最小成本。最后将两部分的最小成本相加，再加上切割的成本 \(\text{cuts}_j - \text{cuts}_i\)。这就是本次切割的最小成本。

切割点 \(\text{cuts}_k\) 将区间 \(\left[ \text{cuts}_i, \text{cuts}_j \right]\) 分成了 \(\left[ \text{cuts}_i, \text{cuts}_k \right]\) 和 \(\left[ \text{cuts}_k, \text{cuts}_j \right]\) 两部分。因此，dp[i][j] 的值可以通过 dp[i][k] 和 dp[k][j] 推导出来。

因此状态转移方程为：

\[ \text{dp}_{i,j} = \min(\text{dp}_{i,j} \ ,\ \text{dp}_{i,k} + \text{dp}_{k,j} + \text{cuts}_j - \text{cuts}_i) \]

通过这个状态转移方程，我们可以递归地计算出在任意两个切割点之间切割的最小成本，最终得到整个棍子的最小切割成本。

具体步骤如下：

  • 首先对 cuts 进行排序，以确保按从小到大的顺序进行切割。
  • 初始化 dp[i][j] 二维数组，高度和宽度均为 len(cuts) + 2。
  • 从长度为 2 的区间开始，逐步增加长度，直到长度为 len(cuts)。
  • 在每个长度下，遍历所有的区间，计算出最小成本。
  • 最终返回 dp[0][len(cuts) - 1] 即可。

完整题解

class Solution:
    def minCost(self, n: int, cuts: list[int]) -> int:

        # 添加 0 和 n 作为边界，并排序
        cuts = [0] + sorted(cuts) + [n]
        m = len(cuts)

        dp = [[0] * m for _ in range(m)]

        for length in range(2, m):
            for i in range(m - length):
                j = i + length
                dp[i][j] = float('inf')
                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][m - 1]

复杂度分析

  • 时间复杂度：\(O(n^3)\)，其中 \(n\) 是 cuts 的长度。
  • 空间复杂度：\(O(n^2)\)。

评论