区间动态规划例题：切棍子的最小成本问题 题目描述 你有一根长度为 n 的木棍，标记了从 0 到 n 的刻度。同时给定一个整数数组 cuts ，表示需要在这根木棍上切割的位置（这些位置保证在 (0, n) 范围内）。每次切割的成本等于当前木棍的长度。要求按某种顺序切割所有指定位置，使得总成本最小。返回最小的总切割成本。 示例 输入： n = 7 , cuts = [1, 3, 4, 5] 输出： 16 解释：按顺序 [1, 3, 4, 5] 切割，总成本 = 7 + 6 + 4 + 3 = 20，但最优顺序下成本可降至 16。 解题思路 问题分析 每次切割的成本是当前木棍的长度，因此我们希望先切割较短的木棍，以减少后续成本。 若将 cuts 排序并加入边界 0 和 n ，则问题转化为在连续区间 [left, right] 上选择切割点的最优顺序。 区间动态规划定义 定义 dp[i][j] 表示在区间 [sticks[i], sticks[j]] 内（即第 i 到第 j 个切割点之间的木棍）完成所有切割的最小成本。 初始时， sticks 数组由 [0] + sorted(cuts) + [n] 构成，长度为 m 。 区间长度 len 从 2 开始遍历（至少包含一个切割点），逐步扩大。 状态转移方程 对于区间 [i, j] ，若其中存在切割点（即 j > i+1 ），我们枚举第一个切割点 k （ i < k < j ）： \[ dp[ i][ j] = \min_ {k \in (i, j)} \left( dp[ i][ k] + dp[ k][ j] + (sticks[ j] - sticks[ i ]) \right) \] sticks[j] - sticks[i] 是当前木棍的长度，即切割成本。 dp[i][k] 和 dp[k][j] 分别表示切割左右两部分的最小成本。 初始化与遍历顺序 初始化： dp[i][i+1] = 0 （区间内无切割点，无需成本）。 遍历时按区间长度从小到大进行，确保子问题已计算。 结果提取 最终结果为 dp[0][m-1] ，即整个木棍 [0, n] 的切割最小成本。 详细步骤（以示例为例） 输入： n = 7 , cuts = [1, 3, 4, 5] 构造 sticks = [0, 1, 3, 4, 5, 7] ，长度 m = 6 。 初始化 dp 表（6×6），所有 dp[i][i+1] = 0 ： 计算区间长度 len = 3 （包含 1 个切割点）： [0, 3] ：切割点 k=1 ，成本 = dp[0][1] + dp[1][3] + (3-0) = 0 + 0 + 3 = 3 [1, 4] ：切割点 k=2 ，成本 = 0 + 0 + (4-1) = 3 同理计算其他区间。 计算区间长度 len = 4 （包含 2 个切割点）： [0, 4] ：枚举切割点 k=1 或 k=2 ： k=1 ：成本 = dp[0][1] + dp[1][4] + (4-0) = 0 + 3 + 4 = 7 k=2 ：成本 = dp[0][2] + dp[2][4] + 4 = 3 + 0 + 4 = 7 取最小值 7 。 最终计算 [0, 5] （整个木棍）： 枚举 k=1,2,3,4 ，最小成本为 16 （通过 k=3 或 k=4 得到）。 关键点 将切割点排序并加入边界，转化为区间划分问题。 区间 DP 通过枚举第一个切割点，将问题分解为左右子区间。 时间复杂度 O(m³)，空间复杂度 O(m²)，其中 m = len(cuts) + 2 。