Description
給定一根長度為
n的木棍和一組切割點cuts。每次切割的成本等於被切的那段木棍長度。可以任意順序切割，回傳最小總成本。
Example:
Input: n = 7, cuts = [1,3,4,5] Output: 16
Intuition#
區間 DP：
dp[i][j]表示切完第i到第j個切割點之間所有切割的最小成本。
- 將
cuts排序並加入 0 和 n 作為端點 dp[i][j]表示將cuts[i]到cuts[j]這段完全切好的最小成本- 枚舉中間切割點
k，成本為cuts[j] - cuts[i] + dp[i][k] + dp[k][j] - 經典的區間 DP（類似 Burst Balloons）
Approaches#
1: 記憶化搜索#
- 概念: Top-down 遞迴，
dfs(i, j)回傳切完cuts[i]到cuts[j]之間的最小成本。 - 時間複雜度:
O(c^3)，c 為切割點數 - 空間複雜度:
O(c^2)
class Solution {
fun minCost(n: Int, cuts: IntArray): Int {
val sortedCuts = (intArrayOf(0) + cuts.sorted() + intArrayOf(n))
val m = sortedCuts.size
val memo = Array(m) { IntArray(m) { -1 } }
fun dfs(i: Int, j: Int): Int {
if (j - i <= 1) return 0
if (memo[i][j] != -1) return memo[i][j]
var best = Int.MAX_VALUE
for (k in i + 1 until j) {
best = minOf(best, dfs(i, k) + dfs(k, j) + sortedCuts[j] - sortedCuts[i])
}
memo[i][j] = best
return best
}
return dfs(0, m - 1)
}
}⭐2: Bottom-up 區間 DP#
- 概念: 從短區間到長區間填表，
dp[i][j]為切完cuts[i]到cuts[j]之間的最小成本。 - 時間複雜度:
O(c^3) - 空間複雜度:
O(c^2)
class Solution {
fun minCost(n: Int, cuts: IntArray): Int {
val sortedCuts = (intArrayOf(0) + cuts.sorted() + intArrayOf(n))
val m = sortedCuts.size
val dp = Array(m) { IntArray(m) }
for (len in 2 until m) {
for (i in 0 until m - len) {
val j = i + len
dp[i][j] = Int.MAX_VALUE
for (k in i + 1 until j) {
dp[i][j] = minOf(dp[i][j], dp[i][k] + dp[k][j] + sortedCuts[j] - sortedCuts[i])
}
}
}
return dp[0][m - 1]
}
}🔑 Takeaways#
- Pattern: 區間 DP — 與 Burst Balloons (312) 結構相同
- 關鍵技巧: 排序切割點並加入兩端作為邊界；切割成本 = 當前段長度
cuts[j] - cuts[i]，與切割順序無關