1547. 切棍子的最小成本

发表于 分类于 阅读次数： Waline： 本文字数： 970 阅读时长 ≈ 3 分钟

考点

  • 区间DP

思路

1. 问题描述与核心难点

给定一根长度为 \(n\) 的木棍，其初始区间为 \([0, n]\)。 在若干指定位置 cuts[i] 处必须进行切割。

切割规则：

  • 每次对一段长度为 \(L\) 的木棍进行一次切割，代价为 \(L\)；
  • 切割顺序可以任意调整；
  • 所有指定位置最终都必须被切到。

目标是：选择一种切割顺序，使总代价最小。

1.1 直接建模的误区

若尝试以“木棍的物理长度”作为 DP 维度（例如令状态表示区间 \([i, j]\) 的长度），由于 \(n \le 10^6\)，状态规模将达到 \(O(n^2)\)，完全不可行。

因此，状态维度不能建立在长度本身上。

2. 正确的建模思路：以「切点」为状态

2.1 关键观察

切割只会发生在给定的有限个切点上。 切割顺序的不同，只会影响每一刀切时所在区间的长度。

因此：

问题的本质并不依赖于 \(n\) 的大小，而只依赖于 切点的数量。

2.2 切点预处理

将所有切点统一放入一个数组，并补上左右端点： \[ a = \{0\} \cup \text{cuts} \cup \{n\} \] 并按升序排序。

设：

  • \(m = |a|\)，即切点总数（包含 0 与 \(n\)）；
  • \(a[i]\) 表示第 \(i\) 个切点的位置。

3. 状态定义（State）

定义二维 DP 数组： \[ f[i][j] = \text{将区间 } (a[i], a[j]) \text{ 内所有切点切完的最小代价} \]

3.1 状态含义说明

  • 区间是开区间 \((a[i], a[j])\)；

  • 若 \(j = i + 1\)，区间内没有任何切点： \[ f[i][i+1] = 0 \]

4. 状态转移方程（Transition）

4.1 转移思路

考虑区间 \((a[i], a[j])\)，若其中至少有一个切点：

  • 设第一次切割选择在切点 \(a[k]\)，其中： \[ i < k < j \]

  • 当前这一刀的代价为整段长度： \[ a[j] - a[i] \]

  • 切完后，问题被分解为左右两个独立子区间：

    • \((a[i], a[k])\)
    • \((a[k], a[j])\)

4.2 转移方程

\[ f[i][j] = \min_{i < k < j} \Big( f[i][k] + f[k][j] + (a[j] - a[i]) \Big) \]

5. 计算顺序（DP 顺序）

由于 \(f[i][j]\) 依赖于更短的区间：

  • 按区间长度从小到大枚举；
  • 区间长度用切点下标差表示。

具体做法：

  • 枚举区间长度 \(\text{len} = 3 \sim m\)；

  • 对每个长度，枚举右端点 \(j\)，左端点为： \[ i = j - \text{len} + 1 \]

6. 复杂度分析

  • 状态数：\(O(m^2)\)
  • 每个状态枚举切点：\(O(m)\)

总体时间复杂度： \[ O(m^3) \] 在本题中：

  • \(\text{cuts.length} \le 100\)
  • \(m \le 102\)

因此 \(m^3 \approx 10^6\)，完全可行。

7. AC代码

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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int minCost(int n, vector<int>& cuts) {
        // 将左右端点加入切点集合
        cuts.push_back(0);
        cuts.push_back(n);

        // 对所有切点排序
        sort(cuts.begin(), cuts.end());

        // f[i][j]：将 (cuts[i], cuts[j]) 内所有切点切完的最小代价
        int f[105][105] = {};

        // m 为切点总数（包含 0 与 n）
        int m = cuts.size();

        // 枚举区间长度（至少为 3，才存在内部切点）
        for (int len = 3; len <= m; ++len) {
            // 枚举右端点 j
            for (int j = len - 1; j < m; ++j) {
                int i = j - len + 1;  // 左端点

                int best = INT_MAX >> 1;

                // 枚举第一次切割位置 k
                for (int k = j - 1; k > i; --k) {
                    best = min(
                        best,
                        f[i][k] + f[k][j] + (cuts[j] - cuts[i])
                    );
                }

                f[i][j] = best;
            }
        }

        // 整根木棍 (0, n) 的最小切割代价
        return f[0][m - 1];
    }
};

8. 小结

  • 本题是经典区间 DP 模型；
  • 核心在于：
    • 将问题从「长度空间」映射到「切点空间」；
    • 使用区间划分的思想进行状态转移；
  • 状态转移方程形式高度通用，可作为区间 DP 模板记忆。

该模型在以下问题中也会反复出现：

  • 最优矩阵链乘法
  • 合并石子
  • 戳气球（Burst Balloons）
  • 其他“先选一个分割点，再递归处理左右区间”的最优代价问题