1547-切棍子的最小成本

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:24 2023-09-13 16:06:24 Updated    

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

![](https://assets.leetcode-cn.com/aliyun-lc-
upload/uploads/2020/08/09/statement.jpg)

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

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

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

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

示例 1：

**输入：** n = 7, cuts = [1,3,4,5]
**输出：** 16
**解释：** 按 [1, 3, 4, 5] 的顺序切割的情况如下所示：
![](https://assets.leetcode-cn.com/aliyun-lc-upload/uploads/2020/08/09/e11.jpg)
第一次切割长度为 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 数组中的所有整数都 互不相同

前言

本题和 312. 戳气球 较为相似，都是经典的区间动态规划题。

方法一：动态规划

思路与算法

在我们任意一次切割时，待切割木棍的左端点要么是原始木棍的左端点 0，要么是之前某一次切割的位置；同理，待切割木棍的右端点要么是原始木棍的右端点 n，要么是之前某一次切割的位置。

因此，如果我们将切割位置数组 cuts 进行排序，并在左侧添加 0，右侧添加 n，那么待切割的木棍就对应着数组中一段连续的区间。这样一来，我们就可以用动态规划来解决本题。

我们用数组 cuts}[1..m] 表示题目中给定的数组 cuts 按照升序排序后的结果，其中 m 是数组 cuts 的长度，并令 cuts[0] = 0，cuts[m+1] = n。同时，我们用 f[i][j] 表示在当前待切割的木棍的左端点为 cuts}[i-1]，右端点为 cuts}[j+1] 时，将木棍全部切开的最小总成本。

这里全部切开的意思是，木棍中有 j-i+1 个切割位置 cuts}[i], \cdots, \textit{cuts}[j]，我们需要将木棍根据这些位置，切割成 j-i+2 段。

为了得到最小总成本，我们可以枚举第一刀的位置。如果第一刀的位置为 cuts}[k]，其中 k \in [i, j]，那么我们会将待切割的木棍分成两部分，左侧部分的木棍为 cuts}[i-1..k]，对应的可以继续切割的位置为 cuts}[i..k-1]；右侧部分的木棍为 cuts}[k..j+1]，对应的可以继续切割的位置为 cuts}[k+1..j]。由于左右两侧均为规模较小的子问题，因此我们可以得到状态转移方程：

f[i][j] = \min_{k \in [i,j]} { f[i][k-1] + f[k+1][j] } + (\textit{cuts}[j+1] - \textit{cuts}[i-1])

即我们无论在哪里切第一刀，这一刀的成本都是木棍的长度 cuts}[j+1] - \textit{cuts}[i-1]。

状态转移方程的边界条件为：

f[i][j] = 0, 其中 i > j

也就是说，如果没有可以切割的位置，那么它要么是一根无法再切割的木棍（此时 i=j+1），要么根本就不是一根木棍（此时 i>j+1）。无论是哪一种情况，对应的最小总成本都是 0。

最后的答案即为 f[1][m]。

细节

在区间动态规划中，我们要注意状态计算的顺序，即在计算 f[i][j] 时，所有满足 k \in [i, j] 的 f[i][k] 和 f[k][j] 都需要已经被计算过。

代码

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        int m = cuts.size();
        sort(cuts.begin(), cuts.end());
        cuts.insert(cuts.begin(), 0);
        cuts.push_back(n);
        vector<vector<int>> f(m + 2, vector<int>(m + 2));
        for (int i = m; i >= 1; --i) {
            for (int j = i; j <= m; ++j) {
                f[i][j] = (i == j ? 0 : INT_MAX);
                for (int k = i; k <= j; ++k) {
                    f[i][j] = min(f[i][j], f[i][k - 1] + f[k + 1][j]);
                }
                f[i][j] += cuts[j + 1] - cuts[i - 1];
            }
        }
        return f[1][m];
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int minCost(int n, int[] cuts) {
        int m = cuts.length;
        Arrays.sort(cuts);
        int[] newCuts = new int[m + 2];
        newCuts[0] = 0;
        for (int i = 1; i <= m; ++i) {
            newCuts[i] = cuts[i - 1];
        }
        newCuts[m + 1] = n;
        int[][] f = new int[m + 2][m + 2];
        for (int i = m; i >= 1; --i) {
            for (int j = i; j <= m; ++j) {
                f[i][j] = i == j ? 0 : Integer.MAX_VALUE;
                for (int k = i; k <= j; ++k) {
                    f[i][j] = Math.min(f[i][j], f[i][k - 1] + f[k + 1][j]);
                }
                f[i][j] += newCuts[j + 1] - newCuts[i - 1];
            }
        }
        return f[1][m];
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minCost(self, n: int, cuts: List[int]) -> int:
        m = len(cuts)
        cuts = [0] + sorted(cuts) + [n]
        f = [[0] * (m + 2) for _ in range(m + 2)]

        for i in range(m, 0, -1):
            for j in range(i, m + 1):
                f[i][j] = 0 if i == j else \
                    min(f[i][k - 1] + f[k + 1][j] for k in range(i, j + 1))
                f[i][j] += cuts[j + 1] - cuts[i - 1]
        
        return f[1][m]
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int comp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int minCost(int n, int* cuts, int cutsSize) {
    qsort(cuts, cutsSize, sizeof(int), comp);
    int* tmp = malloc(sizeof(int) * (cutsSize + 2));
    for (int i = 0; i < cutsSize; i++) {
        tmp[i + 1] = cuts[i];
    }
    tmp[0] = 0, tmp[cutsSize + 1] = n;
    int f[cutsSize + 2][cutsSize + 2];
    memset(f, 0, sizeof(f));
    for (int i = cutsSize; i >= 1; --i) {
        for (int j = i; j <= cutsSize; ++j) {
            f[i][j] = (i == j ? 0 : INT_MAX);
            for (int k = i; k <= j; ++k) {
                f[i][j] = fmin(f[i][j], f[i][k - 1] + f[k + 1][j]);
            }
            f[i][j] += tmp[j + 1] - tmp[i - 1];
        }
    }
    free(tmp);
    return f[1][cutsSize];
}

复杂度分析

  • 时间复杂度：O(m^3)，其中 m 是数组 cuts 的长度。状态的数量为 O(m^2)，转移的时间复杂度为 O(m)，相乘即可得到总时间复杂度。此外，将数组 cuts 进行排序的时间复杂度以及插入 0 和 n 的时间复杂度在渐进意义下小于 O(m^3)，因此可以忽略不计。

  • 空间复杂度：O(m^2)，即为存储所有状态需要的空间。

 Comments
On this page
1547-切棍子的最小成本