题干与适用场景
木棍端点为 0 和 n，数组 cuts 给出互不相同的内部切点。每次选择当前一段中的一个切点，支付该段长度，再把它分成左右两段。约束可采用 LeetCode 1547 的量级：n 不超过 1,000,000，切点数量 m 不超过 100。目标是总成本最小，不要求输出切割顺序；若要恢复顺序，需要额外记录决策点。
面试官考察点
- 能否识别“切割顺序影响子问题”的区间 DP，而不是按输入顺序贪心。
- 能否补上 0 和 n 两个哨兵，并把切点排序。
- 能否解释为什么第一刀或最后一刀能把区间拆成两个独立子问题。
- 能否给出 m 维状态的时间、空间复杂度和溢出边界。
回答前需要澄清的问题
- cuts 是否可能包含 0、n 或重复值？若可能，应先去重并明确非法输入策略。
- 只需要最小成本，还是还要返回一组最优切割顺序？后者需要保存选择 k。
- m 的上限是多少？若 m 很大，O(m³) 是否可接受会改变方案。
- 成本是否始终等于当前段长度？若成本带权，转移中的区间长度需要替换。
30 秒回答框架
我先排序切点并加入 0、n。令 dp[i][j] 表示完成 cuts[i] 与 cuts[j] 之间所有切割的最小成本；相邻端点之间没有内部切点，所以值为 0。对区间尝试每个内部切点 k 作为第一刀，成本是右端点减左端点，加左右两个子区间的最优值。按区间长度递增填表，答案是 dp[0][m+1]，时间 O(m³)，空间 O(m²)。
分步骤深入解答
1. 先固定坐标和输入不变量
把 cuts 排序，构造 points = 0、所有切点、n。排序后区间 points[i] 到 points[j] 的内部切点恰好是索引 i+1 到 j-1。这个不变量让状态只依赖端点索引，而不依赖切割发生的历史顺序。
2. 定义区间状态
dp[i][j] 表示完成所有严格位于 points[i] 与 points[j] 之间的切割所需最小成本。若 j 等于 i+1，区间没有内部切点，dp 为 0。状态不记录已经切过的顺序，因为一旦第一刀确定，左右两侧互不影响，且后续每刀成本只由所属子段长度决定。
3. 推导转移
若第一刀选 points[k]，其中 i 小于 k 且 k 小于 j，则当前支付 points[j] 减 points[i]。这刀把问题分成左右两个独立区间，因此：
dp[i][j] = min(
dp[i][k] + dp[k][j] + points[j] - points[i]
for k in (i + 1 ... j - 1)
)只要按区间跨度从小到大计算，dp[i][k] 和 dp[k][j] 在使用时已经完成。
4. 给出可执行实现
function minCost(n: number, cuts: number[]): number {
const points = [0, ...cuts.slice().sort((a, b) => a - b), n];
const m = points.length;
const dp = Array.from({ length: m }, () => Array<number>(m).fill(0));
for (let span = 2; span < m; span += 1) {
for (let left = 0; left + span < m; left += 1) {
const right = left + span;
let best = Number.POSITIVE_INFINITY;
for (let pivot = left + 1; pivot < right; pivot += 1) {
best = Math.min(
best,
dp[left][pivot] + dp[pivot][right] + points[right] - points[left],
);
}
dp[left][right] = best === Number.POSITIVE_INFINITY ? 0 : best;
}
}
return dp[0][m - 1];
}5. 证明状态转移正确
对内部切点数量做归纳。零个切点时成本为 0，基例成立。假设更短区间都能求得最优值。任意最优切割顺序都有第一刀 k；该刀成本固定为整个区间长度，之后左右子段互不影响，按归纳假设分别取 dp[i][k] 和 dp[k][j] 得到该第一刀下的最优成本。枚举全部 k 取最小值，覆盖所有可能的第一刀，因此状态最优。
6. 复杂度、数值和恢复路径
设内部切点数量为 m，状态数量是 O(m²)，每个状态最多枚举 O(m) 个 pivot，因此时间 O(m³)，空间 O(m²)。n 可到 1,000,000，m 只有 100 时总成本约为 m 乘 n 的量级，JavaScript number 足以覆盖题设；若业务上 n 或成本权重可能超过安全整数，应改用 BigInt 或安全整数检查。要恢复顺序，就为每个 dp[i][j] 保存使 best 最小的 pivot，再递归输出。
7. 反例与测试
输入 n=7、cuts=[1,3,4,5] 时，按输入顺序切成本为 20，而选择 3、5、1、4 可得到 16，说明输入顺序和从左到右都不保证最优。测试还应覆盖单个切点、切点靠近端点、非排序输入、重复值策略、连续间隔、最大 m，以及所有切点都被处理后的零内部区间。
高质量示范回答
我会先排序切点并加上 0 和 n。dp[i][j] 表示完成两端之间所有切割的最小成本，相邻端点的值为 0。枚举第一刀 k：当前段一次支付 points[j] 减 points[i]，左右结果独立，所以取 dp[i][k] 加 dp[k][j] 加段长的最小值。按跨度递增填表，答案在最外层区间。m 个切点时复杂度是 O(m³) 时间、O(m²) 空间；如果还要顺序，就保存最优 pivot。用非排序输入、端点附近切点、单点和题目给出的 7、[1,3,4,5] 反例验证。
常见错误
- 按 cuts 输入顺序切 → 顺序可能远离最优 → 排序后用区间 DP 枚举第一刀。
- 忘记加入 0 和 n → 边界区间长度或状态不完整 → 把端点作为哨兵纳入 points。
- 把 dp[i][j] 写成“切一刀的成本” → 忽略子区间后续切割 → 明确定义为完成整个内部集合的最小成本。
- 用当前区间最短或最长的贪心切点 → 局部选择影响左右总成本 → 给出递归分解和归纳证明。
- 只测排序输入 → 代码可能隐含输入有序 → 在函数内部复制并排序，测试乱序数组。
追问及应对
如果还要返回一组切割顺序怎么办？
为每个区间保存达到最小值的 pivot。先输出该 pivot，再递归左右区间即可得到一棵切割决策树；若多个 pivot 同成本，明确采用最小索引或字典序规则。
如果 m 从 100 增长到 2,000，O(m³) 还能接受吗？
通常不应直接承诺。先测量状态数和时间预算，再考虑题目是否存在额外结构、近似方案或离线限制。不能仅因区间 DP 熟悉就声称有通用 O(m²) 优化；需要新的单调性或四边形不等式证明。
如果 cuts 包含重复位置呢？
重复切同一位置没有第二次有效切割。可以先排序去重，或按题目契约拒绝重复输入；两种策略的选择必须写进 API 语义和测试，而不能让重复点产生零长度区间。
如果每刀成本是当前段长度乘权重呢？
若权重只由被选位置 k 决定，转移把段长替换为段长乘 weight[k]，区间拆分仍成立。若成本依赖历史切割顺序、已切数量或跨区间状态，左右子问题就不再独立，需要重新定义状态。