题目描述
有一根长度为 n
个单位的木棍,棍上从 0
到 n
标记了若干位置。例如,长度为 6 的棍子可以标记如下:
给你一个整数数组 cuts
,其中 cuts[i]
表示你需要将棍子切开的位置。
你可以按顺序完成切割,也可以根据需要更改切割的顺序。
每次切割的成本都是当前要切割的棍子的长度,切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍(这两根木棍的长度和就是切割前木棍的长度)。请参阅第一个示例以获得更直观的解释。
返回切棍子的 最小总成本 。
示例 1:
输入: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)。
示例 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
数组中的所有整数都 互不相同
解法
方法一:动态规划(区间 DP)
我们可以往切割点数组 $\textit{cuts}$ 中添加两个元素,分别是 $0$ 和 $n$,表示棍子的两端。然后我们对 $\textit{cuts}$ 数组进行排序,这样我们就可以将整个棍子切割为若干个区间,每个区间都有两个切割点。不妨设此时 $\textit{cuts}$ 数组的长度为 $m$。
接下来,我们定义 $\textit{f}[i][j]$ 表示切割区间 $[\textit{cuts}[i],..\textit{cuts}[j]]$ 的最小成本。
如果一个区间只有两个切割点,也就是说,我们无需切割这个区间,那么 $\textit{f}[i][j] = 0$。
否则,我们枚举区间的长度 $l$,其中 $l$ 等于切割点的数量减去 $1$。然后我们枚举区间的左端点 $i$,右端点 $j$ 可以由 $i + l$ 得到。对于每个区间,我们枚举它的切割点 $k$,其中 $i \lt k \lt j$,那么我们可以将区间 $[i, j]$ 切割为 $[i, k]$ 和 $[k, j]$,此时的成本为 $\textit{f}[i][k] + \textit{f}[k][j] + \textit{cuts}[j] - \textit{cuts}[i]$,我们取所有可能的 $k$ 中的最小值,即为 $\textit{f}[i][j]$ 的值。
最后,我们返回 $\textit{f}[0][m - 1]$。
时间复杂度 $O(m^3)$,空间复杂度 $O(m^2)$。其中 $m$ 为修改后的 $\textit{cuts}$ 数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12
13 | class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
cuts.extend([0, n])
cuts.sort()
m = len(cuts)
f = [[0] * m for _ in range(m)]
for l in range(2, m):
for i in range(m - l):
j = i + l
f[i][j] = inf
for k in range(i + 1, j):
f[i][j] = min(f[i][j], f[i][k] + f[k][j] + cuts[j] - cuts[i])
return f[0][-1]
|
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) {
List<Integer> nums = new ArrayList<>();
for (int x : cuts) {
nums.add(x);
}
nums.add(0);
nums.add(n);
Collections.sort(nums);
int m = nums.size();
int[][] f = new int[m][m];
for (int l = 2; l < m; ++l) {
for (int i = 0; i + l < m; ++i) {
int j = i + l;
f[i][j] = 1 << 30;
for (int k = i + 1; k < j; ++k) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + nums.get(j) - nums.get(i));
}
}
}
return f[0][m - 1];
}
}
|
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) {
cuts.push_back(0);
cuts.push_back(n);
sort(cuts.begin(), cuts.end());
int m = cuts.size();
int f[110][110]{};
for (int l = 2; l < m; ++l) {
for (int i = 0; i + l < m; ++i) {
int j = i + l;
f[i][j] = 1 << 30;
for (int k = i + 1; k < j; ++k) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j] + cuts[j] - cuts[i]);
}
}
}
return f[0][m - 1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | func minCost(n int, cuts []int) int {
cuts = append(cuts, []int{0, n}...)
sort.Ints(cuts)
m := len(cuts)
f := make([][]int, m)
for i := range f {
f[i] = make([]int, m)
}
for l := 2; l < m; l++ {
for i := 0; i+l < m; i++ {
j := i + l
f[i][j] = 1 << 30
for k := i + 1; k < j; k++ {
f[i][j] = min(f[i][j], f[i][k]+f[k][j]+cuts[j]-cuts[i])
}
}
}
return f[0][m-1]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | function minCost(n: number, cuts: number[]): number {
cuts.push(0, n);
cuts.sort((a, b) => a - b);
const m = cuts.length;
const f: number[][] = Array.from({ length: m }, () => Array(m).fill(0));
for (let l = 2; l < m; l++) {
for (let i = 0; i < m - l; i++) {
const j = i + l;
f[i][j] = Infinity;
for (let k = i + 1; k < j; k++) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + cuts[j] - cuts[i]);
}
}
}
return f[0][m - 1];
}
|
方法二:动态规划(另一种枚举方式)
我们也可以从大到小枚举 $i$,从小到大枚举 $j$,这样可以保证在计算 $f[i][j]$ 时,状态 $f[i][k]$ 和 $f[k][j]$ 都已经被计算过了,其中 $i \lt k \lt j$。
时间复杂度 $O(m^3)$,空间复杂度 $O(m^2)$。其中 $m$ 为修改后的 $\textit{cuts}$ 数组的长度。
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
cuts.extend([0, n])
cuts.sort()
m = len(cuts)
f = [[0] * m for _ in range(m)]
for i in range(m - 1, -1, -1):
for j in range(i + 2, m):
f[i][j] = inf
for k in range(i + 1, j):
f[i][j] = min(f[i][j], f[i][k] + f[k][j] + cuts[j] - cuts[i])
return f[0][-1]
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22 | class Solution {
public int minCost(int n, int[] cuts) {
List<Integer> nums = new ArrayList<>();
for (int x : cuts) {
nums.add(x);
}
nums.add(0);
nums.add(n);
Collections.sort(nums);
int m = nums.size();
int[][] f = new int[m][m];
for (int i = m - 1; i >= 0; --i) {
for (int j = i + 2; j < m; ++j) {
f[i][j] = 1 << 30;
for (int k = i + 1; k < j; ++k) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + nums.get(j) - nums.get(i));
}
}
}
return f[0][m - 1];
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public:
int minCost(int n, vector<int>& cuts) {
cuts.push_back(0);
cuts.push_back(n);
sort(cuts.begin(), cuts.end());
int m = cuts.size();
int f[110][110]{};
for (int i = m - 1; ~i; --i) {
for (int j = i + 2; j < m; ++j) {
f[i][j] = 1 << 30;
for (int k = i + 1; k < j; ++k) {
f[i][j] = min(f[i][j], f[i][k] + f[k][j] + cuts[j] - cuts[i]);
}
}
}
return f[0][m - 1];
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 | func minCost(n int, cuts []int) int {
cuts = append(cuts, []int{0, n}...)
sort.Ints(cuts)
m := len(cuts)
f := make([][]int, m)
for i := range f {
f[i] = make([]int, m)
}
for i := m - 1; i >= 0; i-- {
for j := i + 2; j < m; j++ {
f[i][j] = 1 << 30
for k := i + 1; k < j; k++ {
f[i][j] = min(f[i][j], f[i][k]+f[k][j]+cuts[j]-cuts[i])
}
}
}
return f[0][m-1]
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | function minCost(n: number, cuts: number[]): number {
cuts.push(0);
cuts.push(n);
cuts.sort((a, b) => a - b);
const m = cuts.length;
const f: number[][] = Array.from({ length: m }, () => Array(m).fill(0));
for (let i = m - 2; i >= 0; --i) {
for (let j = i + 2; j < m; ++j) {
f[i][j] = 1 << 30;
for (let k = i + 1; k < j; ++k) {
f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j] + cuts[j] - cuts[i]);
}
}
}
return f[0][m - 1];
}
|