題幹與適用場景
木棍端點為 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]，區間拆分仍成立。若成本依賴歷史切割順序、已切數量或跨區間狀態，左右子問題就不再獨立，需要重新定義狀態。