解題說明
Minimum Cost to Cut a Stick
題目描述：
有一根長度為 n 的木棍和一組切割位置 cuts。每次切割一段木棍的成本等於該段木棍的長度。你可以任意安排切割順序，求完成所有切割的最小總成本。
解題思路： 這是經典的區間 DP 問題。
- 將
cuts排序，並在頭尾加上 0 和 n，形成新陣列c = [0, cuts[0], cuts[1], ..., cuts[m-1], n]。 - 定義
dp[i][j]為切割c[i]到c[j]這段木棍上所有切割點的最小成本。 - 轉移：枚舉中間的切割點 k（i < k < j），
dp[i][j] = min(dp[i][k] + dp[k][j]) + (c[j] - c[i])。每次切割的成本是當前木棍的長度c[j] - c[i]。 - 基礎情況：
dp[i][i+1] = 0（相鄰兩點間無切割點）。 - 答案為
dp[0][m+1]。
C++ 解法
複雜度分析
時間複雜度：O(m^3) — m 為切割點數量。三層迴圈（區間長度、左端點、中間點）。
空間複雜度：O(m^2) — DP 表格大小。
虛擬碼
1. Sort cuts, prepend 0 and append n to form array c
2. Let sz = c.length
3. Create dp[sz][sz] initialized to 0
4. For len from 2 to sz-1:
For i from 0 to sz-len-1:
j = i + len
dp[i][j] = infinity
For k from i+1 to j-1:
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j])
dp[i][j] += c[j] - c[i]
5. Return dp[0][sz-1]其他解法
記憶化遞迴（Top-Down）：定義 solve(i, j) 為切割 c[i] 到 c[j] 的最小成本。遞迴搭配記憶化。邏輯等價，但遞迴可能更直觀。
Knuth 優化 O(m^2)：利用 Knuth 的四邊形不等式優化，將最內層迴圈的搜尋範圍縮小。證明較複雜，但可將時間從 O(m^3) 降至 O(m^2)。
延伸思考
- 此問題與「矩陣鏈乘法」和「最優二叉搜尋樹」有什麼結構相似之處？
- 若切割點的數量很大（例如 10^4），O(m^3) 是否可行？有什麼加速方法？
- 若每個切割位置有不同的額外成本（不僅是木棍長度），DP 轉移方程如何修改？