NeetCode #749LC-1547Hard2-D Dynamic Programming
← Back to All Problems#749 · #1547 · Minimum Cost to Cut a Stick(切棍子的最小成本)
📌 Problem Statement & Constraints
A wooden stick of length
n has cut positions cuts. Each cut costs the length of the stick being cut at that moment. Return the minimum total cost to perform every cut. Constraints: 2 <= n <= 10^6, 1 <= cuts.length <= 100, 1 <= cuts[i] <= n - 1, and all cuts[i] are distinct.💡 Core Algorithmic Approaches
- Add the endpoints
0andnto the cut list and sort it; the segments between consecutive boundaries are the subproblems. - Let
dp[i][j]be the minimum cost to perform every cut strictly between boundariescuts[i]andcuts[j]. - The first cut inside the segment can be any
kwithi < k < j; it costscuts[j] - cuts[i]and splits the problem intodp[i][k]anddp[k][j]. - So
dp[i][j] = cuts[j] - cuts[i] + min over k of (dp[i][k] + dp[k][j]), filled by increasing segment width.
💻 Benchmark Python3 Implementation
class Solution:
def minCost(self, n: int, cuts: List[int]) -> int:
cuts = sorted(cuts + [0, n])
m = len(cuts)
# dp[i][j] = min cost to make every cut strictly between cuts[i] and cuts[j]
dp = [[0] * m for _ in range(m)]
for span in range(2, m): # number of gaps in the segment
for i in range(m - span):
j = i + span
best = float("inf")
for k in range(i + 1, j):
best = min(best, dp[i][k] + dp[k][j])
dp[i][j] = best + cuts[j] - cuts[i]
return dp[0][m - 1]⚡ Complexity Deep Dive
⏱️ Time Complexity
O(m^3) where m = cuts.length + 2: O(m^2) intervals each trying O(m) split points.
💾 Space Complexity
O(m^2): the interval table.
⚠️ Interview Pitfalls & Follow-ups
- Forgetting the endpoints 0 and n: without them the first and last segments cannot be represented, and the cost formula has no anchor.
- Not sorting the cuts: the interval DP assumes ordered boundaries.
- Adding the segment length inside the
min: the current cut's costcuts[j] - cuts[i]is paid once per interval, not per split point. - Fixing the cut order: the optimal order is exactly what is being optimised, so all split points must be tried.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.