n = 7
cuts = [1, 3, 4, 5]

16

切棍子的最小成本问题（不同切割顺序成本不同） 题目描述 你有一根长度为 n 的棍子，它需要被切到指定的位置集合 cuts （ cuts 中的每个位置是整数且严格在 (0, n) 之间）。 每次切割的成本等于当前被切割棍子的长度。 你可以选择切割的顺序，问将所有指定位置都切到的最小总成本是多少？ 示例 输入： 输出： 解释： 一种最优切割顺序： 从位置 4 切割（棍子长度 7，成本 7），分成 [ 0,4] 和 [ 4,7 ] 在 [ 0,4 ] 上切位置 1（成本 4） 在 [ 0,4 ] 上切位置 3（成本 4） 在 [ 4,7 ] 上切位置 5（成本 3） 总成本 = 7 + 4 + 4 + 3 = 18？不对，这样不是最优。 我们稍后推导最优顺序和正确输出。 解题思路（区间 DP） 1. 问题转换 我们将 cuts 排序，并在两端加入 0 和 n ，得到新的数组 arr 。 例如： n=7, cuts=[1,3,4,5] 排序 cuts → [1,3,4,5] 加入边界 → arr = [0, 1, 3, 4, 5, 7] 问题变成：对于区间 [arr[i], arr[j]] （其中 j > i+1 ，即区间内至少有一个要切的点），我们要选择一个切点 arr[k] （i < k < j）先切，然后递归处理左右两个子区间。 2. 状态定义 设 dp[i][j] 表示将区间 (arr[i], arr[j]) 内的所有切割点切完的最小成本。 注意： i 和 j 是 arr 的下标，区间长度是 arr[j] - arr[i] 。 3. 状态转移 如果 j == i+1 ，则区间内没有要切的点，成本为 0。 如果 j > i+1 ，我们要选一个切点 k （ i < k < j ）： 先切 arr[k] ，当前这一刀的成本 = arr[j] - arr[i] （当前棍子长度）。 然后切左边区间 (i, k) 和右边区间 (k, j) 。 总成本 = (arr[j] - arr[i]) + dp[i][k] + dp[k][j] 。 我们要枚举所有可能的 k ，取最小值。 4. DP 填表顺序 区间长度从小到大计算。 设 m = len(arr) ，则 i 从 m-2 往下遍历， j 从 i+2 开始往上遍历。 示例演算（n=7, cuts=[ 1,3,4,5 ]） 步骤 1：预处理 arr = [0, 1, 3, 4, 5, 7] ，长度 m=6。 初始化 dp[6][6] 全 0。 步骤 2：计算长度为 2 的区间（即 j=i+2） i=0, j=2 ：区间 (0,3)，切点 k=1，成本 = (3-0) + dp[ 0][ 1] + dp[ 1][ 2 ] = 3 + 0 + 0 = 3 i=1, j=3 ：(1,4)，切点 k=2，成本 = (4-1) = 3 i=2, j=4 ：(3,5)，切点 k=3，成本 = (5-3) = 2 i=3, j=5 ：(4,7)，切点 k=4，成本 = (7-4) = 3 i=0, j=2 到 i=3,j=5 都是只有唯一切点，直接得值。 先记下： dp[ 0][ 2]=3, dp[ 1][ 3]=3, dp[ 2][ 4]=2, dp[ 3][ 5 ]=3。 步骤 3：计算长度为 3 的区间（j=i+3） i=0, j=3 ：区间 (0,4)，切点可 k=1 或 k=2 k=1：成本 = (4-0) + dp[ 0][ 1] + dp[ 1][ 3 ] = 4 + 0 + 3 = 7 k=2：成本 = 4 + dp[ 0][ 2] + dp[ 2][ 3 ] = 4 + 3 + 0 = 7 取 7，dp[ 0][ 3 ]=7 i=1, j=4 ：(1,5)，切点 k=2 或 k=3 k=2：成本 = (5-1)=4 + dp[ 1][ 2] + dp[ 2][ 4 ] = 4 + 0 + 2 = 6 k=3：成本 = 4 + dp[ 1][ 3] + dp[ 3][ 4 ] = 4 + 3 + 0 = 7 取 6，dp[ 1][ 4 ]=6 i=2, j=5 ：(3,7)，切点 k=3 或 k=4 k=3：成本 = (7-3)=4 + dp[ 2][ 3] + dp[ 3][ 5 ] = 4 + 0 + 3 = 7 k=4：成本 = 4 + dp[ 2][ 4] + dp[ 4][ 5 ] = 4 + 2 + 0 = 6 取 6，dp[ 2][ 5 ]=6 步骤 4：计算长度为 4 的区间（j=i+4） i=0, j=4 ：(0,5)，切点 k=1,2,3 k=1：成本 = (5-0)=5 + dp[ 0][ 1] + dp[ 1][ 4 ] = 5 + 0 + 6 = 11 k=2：成本 = 5 + dp[ 0][ 2] + dp[ 2][ 4 ] = 5 + 3 + 2 = 10 k=3：成本 = 5 + dp[ 0][ 3] + dp[ 3][ 4 ] = 5 + 7 + 0 = 12 取 10，dp[ 0][ 4 ]=10 i=1, j=5 ：(1,7)，切点 k=2,3,4 k=2：成本 = (7-1)=6 + dp[ 1][ 2] + dp[ 2][ 5 ] = 6 + 0 + 6 = 12 k=3：成本 = 6 + dp[ 1][ 3] + dp[ 3][ 5 ] = 6 + 3 + 3 = 12 k=4：成本 = 6 + dp[ 1][ 4] + dp[ 4][ 5 ] = 6 + 6 + 0 = 12 取 12，dp[ 1][ 5 ]=12 步骤 5：计算长度为 5 的区间（j=i+5） i=0, j=5 ：(0,7)，切点 k=1,2,3,4 k=1：成本 = 7 + dp[ 0][ 1] + dp[ 1][ 5 ] = 7 + 0 + 12 = 19 k=2：成本 = 7 + dp[ 0][ 2] + dp[ 2][ 5 ] = 7 + 3 + 6 = 16 k=3：成本 = 7 + dp[ 0][ 3] + dp[ 3][ 5 ] = 7 + 7 + 3 = 17 k=4：成本 = 7 + dp[ 0][ 4] + dp[ 4][ 5 ] = 7 + 10 + 0 = 17 取 16，dp[ 0][ 5 ]=16 最终答案 = dp[ 0][ 5 ] = 16。 总结 这道题的核心是： 将切割位置排序并加边界，转化为区间 DP。 状态 dp[i][j] 表示完成区间内所有切割的最小成本。 转移时枚举第一个切割点，成本为当前区间长度加上左右子区间成本。 填表顺序按区间长度从小到大。 时间复杂度：O(m³)，其中 m = cuts.length + 2。