切棍子的最小成本问题 题目描述 有一根长度为 n 的木棍，需要将它切割成若干段。切割的位置由数组 cuts 给出，数组中的每个元素表示距离木棍左端的切割点（单位与 n 一致）。每次切割的成本等于当前被切割木棍的长度。例如，一根长度为 10 的木棍，若在位置 2 切割，则成本为 10。要求按数组 cuts 中给出的所有位置完成切割，并求出最小的总切割成本。 解题思路 将原问题转化为区间动态规划问题： 在 cuts 数组的首尾分别添加 0 和 n ，并排序得到新的切割点数组。 定义 dp[i][j] 表示在区间 [cuts[i], cuts[j]] 这段木棍上，完成所有内部切割点（即 cuts[i+1] 到 cuts[j-1] ）的最小成本。 最终目标是求 dp[0][m-1] ，其中 m 是新区间的长度。 状态转移方程： 若区间内无切割点（即 j - i <= 1 ），则 dp[i][j] = 0 。 否则，枚举区间内第一个切割点 k （ i < k < j ），将区间分为 [i, k] 和 [k, j] 两段，成本为当前区间长度 cuts[j] - cuts[i] 加上左右两段的成本： 需遍历所有可能的 k 取最小值。 逐步推导 假设 n = 10 , cuts = [2, 5, 7] 。 扩展并排序切割点： [0, 2, 5, 7, 10] 。 初始化 dp 表（5×5 矩阵），对角线附近无切割点的区间成本为 0。 计算区间长度 L = 3 的区间（即间隔两个切割点）： 区间 [0, 5] （对应索引 0-2）：内部切割点为 2 （索引 1）。 dp[0][2] = dp[0][1] + dp[1][2] + (5-0) = 0 + 0 + 5 = 5 。 区间 [2, 7] （索引 1-3）：内部切割点为 5 （索引 2）。 dp[1][3] = 0 + 0 + (7-2) = 5 。 区间 [5, 10] （索引 2-4）：内部切割点为 7 （索引 3）。 dp[2][4] = 0 + 0 + (10-5) = 5 。 计算区间长度 L = 4 的区间： 区间 [0, 7] （索引 0-3）：枚举切割点 k=1 或 k=2 。 k=1 ：成本 = dp[0][1] + dp[1][3] + (7-0) = 0 + 5 + 7 = 12 。 k=2 ：成本 = dp[0][2] + dp[2][3] + 7 = 5 + 0 + 7 = 12 。 取最小值 12 。 最终区间 [0, 10] （索引 0-4）：枚举切割点 k=1,2,3 。 k=1 ：成本 = dp[0][1] + dp[1][4] + 10 = 0 + (dp[1][3]+dp[3][4]+(10-2)=5+0+8=13) + 10 = 23 。 k=2 ：成本 = dp[0][2] + dp[2][4] + 10 = 5 + 5 + 10 = 20 。 k=3 ：成本 = dp[0][3] + dp[3][4] + 10 = 12 + 0 + 10 = 22 。 最小成本为 20 。 总结 通过将原问题转化为区间动态规划，按区间长度由小到大计算，最终得到最小成本为 20。该方法的时间复杂度为 O(m³)，其中 m 是切割点数量。