区间动态规划例题：切棍子的最小成本问题（不同切割顺序成本不同）

题目描述

我们有一根长度为 n 的木棍，以及一个数组 cuts[]，其中记录了 m 个必须进行切割的位置（这些位置是整数，且均位于 (0, n) 之间）。
每次切割的成本等于当前切割的木棍的长度。
你可以按任意顺序切割这 m 个位置，但每次只能切一根棍子（切割后棍子分成两段，后续可以分别再切）。
求完成所有切割所需的最小总成本。

示例

• 输入：n = 7, cuts = [1, 3, 4, 5]
• 输出：16
• 解释：
  1. 初始棍子长度 7。
  2. 如果先切位置 4（成本 7），得到两段 [0,4] 和 [4,7]。
  3. 在 [0,4] 中切位置 3（成本 4），得到 [0,3] 和 [3,4]。
  4. 在 [0,3] 中切位置 1（成本 3），得到 [0,1] 和 [1,3]。
  5. 在 [1,3] 中切位置 ? 但 1 已切过，实际上位置 5 在 [4,7] 中切（成本 3）。
     计算总成本时需按顺序累加：
     一种最优顺序为：
  • 先切 3（成本 7）
  • 再切 1（成本 4）
  • 再切 5（成本 4）
  • 再切 4（成本 3）
    总成本 = 7 + 4 + 4 + 3 = 18（非最优）。
    实际上最优顺序可得到 16（后面推导）。

问题分析

这本质是一个 区间 DP 问题，因为：

1. 切割操作将棍子分成更小的区间。
2. 不同切割顺序导致不同的成本（因为每次成本取决于当前区间的长度）。
3. 我们需要在所有可能的切割顺序中找最小总成本。

关键思路

1. 将切割位置排序并扩展
   为了方便处理区间，我们将 cuts 排序，并在两端加入 0 和 n，形成一个新的数组 points。
   例如：n=7, cuts=[1,3,4,5]
points = [0, 1, 3, 4, 5, 7]
   这样，任意两个 points[i] 和 points[j] 就表示一个棍子区间。

2. DP 定义
   设 dp[i][j] 表示完成区间 (points[i], points[j]) 内的所有切割所需的最小成本，其中 i 和 j 是 points 的索引，且 j - i >= 2（因为中间至少有一个切割点才需要切）。

   • 区间长度 = points[j] - points[i]
   • 若中间没有切割点（即 j == i+1），则 dp[i][j] = 0（无需切割）。

3. 状态转移
   对于区间 (i, j)，我们选择第一个切割点 k（i < k < j），它对应原切割位置 points[k]。

   • 先切 k，则当前切割成本 = points[j] - points[i]（当前棍子长度）。
   • 然后，我们需要分别切割左区间 (i, k) 和右区间 (k, j)，它们的最小成本分别为 dp[i][k] 和 dp[k][j]。
     因此：

\[ dp[i][j] = \min_{i

4. 计算顺序
   由于 dp[i][j] 依赖于更小的区间（(i,k) 和 (k,j) 长度更短），我们需要按区间长度从小到大计算。

详细解题步骤

步骤 1：预处理切割点数组

cuts.sort()
points = [0] + cuts + [n]  # 加入边界
m = len(points)            # m = 原 cuts 长度 + 2

步骤 2：DP 数组初始化

dp = [[0] * m for _ in range(m)]
# dp[i][j] 初始为 0，当 j == i+1 时就是 0

步骤 3：按区间长度递推
区间长度 len = 2 到 m-1（因为索引差至少为 2 才有切割点）：

for length in range(2, m):        # length 是 j - i
    for i in range(m - length):
        j = i + length
        if j - i >= 2:
            dp[i][j] = float('inf')
            for k in range(i+1, j):
                cost = (points[j] - points[i]) + dp[i][k] + dp[k][j]
                dp[i][j] = min(dp[i][j], cost)

步骤 4：答案
最终答案是完成整个棍子 (0, n) 内所有切割的最小成本，对应 dp[0][m-1]。

示例推导

输入：n=7, cuts=[1,3,4,5]
排序 cuts → [1,3,4,5]
points = [0,1,3,4,5,7]，索引 0~5。

计算过程（只写关键部分）：

• 区间 (0,5) 长度 7，中间切割点 k 可取 1,2,3,4。
  以 k=2（points[2]=3）为例：
  成本 = (7-0) + dp[0][2] + dp[2][5]
  先算 dp[0][2]：区间 (0,2) 中间只有 k=1（点 1），
  dp[0][2] = (3-0) + dp[0][1] + dp[1][2] = 3 + 0 + 0 = 3
  再算 dp[2][5]：区间 (2,5) 中间有 k=3,4（点 4,5），
  需再分解，最终可算得 dp[2][5] = (7-3) + ... 等。
  通过递推得到最终 dp[0][5] = 16。

验证：
一种最优切割顺序：

1. 切位置 4（成本 7）→ [0,4] 和 [4,7]
2. 切位置 3（在 [0,4] 中，成本 4）→ [0,3] 和 [3,4]
3. 切位置 1（在 [0,3] 中，成本 3）→ [0,1] 和 [1,3]
4. 切位置 5（在 [4,7] 中，成本 3）→ [4,5] 和 [5,7]
   总成本 = 7 + 4 + 3 + 2 = 16。

时间复杂度

• 状态数：O(m²)，m = cuts.length + 2
• 每个状态枚举中间切割点 k：O(m)
• 总复杂度 O(m³)，在 m ≤ 100 时可行。

总结

本题是经典的 区间 DP 在切割问题上的应用：

1. 将原切割点扩展为区间端点。
2. 定义 dp[i][j] 为完成区间内所有切割的最小成本。
3. 转移时枚举第一个切割点，将区间分成左右子区间。
4. 按区间长度从小到大递推。