Min Cost to Cut a Stick: Interval DP, Explained
Solve Min Cost to Cut a Stick with interval DP — why cut order matters, the memoized recursion, a worked walkthrough, JavaScript code, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Cutting a wooden stick sounds like it should have one obvious answer — just cut at every marked spot. But there's a twist: each cut costs the current length of the piece you're cutting, and you get to choose the order. Cut the same set of marks in a different sequence and your bill changes.
That single detail turns a trivial-looking task into one of the cleanest examples of interval dynamic programming you'll meet in interviews. The greedy instinct — cut wherever, in whatever order — quietly overpays, and the fix is to think in terms of segments between cuts rather than the cuts themselves.
Get the reframe here and you've got the template for a whole family of "combine two sub-ranges" DP problems.
The problem
You have a wooden stick of length n, laid out from position 0 to position n. An array cuts lists the positions where you must make a cut. You can perform the cuts in any order. The cost of one cut equals the length of the stick piece it lands on, and the total cost is the sum of all cut costs. Return the minimum total cost.
Input: n = 7, cuts = [1, 3, 4, 5]
Output: 16
Input: n = 7, cuts = [1, 3]
Output: 10 // cut at 3 first (cost 7), then cut at 1 (cost 3)Two facts drive the whole solution:
- The cost of a cut depends on the piece it's on, and that piece shrinks as you make earlier cuts — so order changes the total.
- Once you cut a stick into two pieces, those pieces are completely independent. Nothing you do on the left half affects the cost of the right half.
That independence is the seam the DP pries open.
The brute force baseline
The literal interpretation: try every possible order of the cuts, simulate the cost, keep the cheapest. With m cuts there are m! orderings.
function minCostBrute(n, cuts) {
let best = Infinity;
function permute(remaining, segments) {
if (remaining.length === 0) { best = Math.min(best, 0); return; }
for (let i = 0; i < remaining.length; i++) {
const c = remaining[i];
// find the segment [lo, hi] that contains cut c
const seg = segments.find(([lo, hi]) => lo < c && c < hi);
const cost = seg[1] - seg[0];
const rest = remaining.filter((_, j) => j !== i);
const nextSegs = segments.flatMap(s =>
s === seg ? [[s[0], c], [c, s[1]]] : [s]);
// recurse and add this cut's cost to whatever the rest costs
// (omitted bookkeeping for brevity)
}
}
permute(cuts, [[0, n]]);
return best;
}The problem: m! explodes. Ten cuts is already 3.6 million orderings; thirteen cuts is over six billion. And it re-solves the same sub-stick over and over — the cost of optimally cutting the segment from position 3 to position 7 is the same no matter when you reach it. Brute force never notices that repetition.
The key insight: think about the last-standing segment
Stop tracking which cut happens first overall. Instead, zoom into one segment of the stick — say the piece between position start and position end — and ask: among the cuts that fall inside this segment, which one do I make first?
Whichever cut c you pick as the first cut inside (start, end):
- You pay the full segment length
end - startfor it (the piece is still whole when you cut it). - That splits the segment into
(start, c)and(c, end), which are now independent sub-problems.
So the cost of optimally clearing segment (start, end) is:
minCost(start, end) =
min over every cut c strictly inside (start, end) of:
(end - start) + minCost(start, c) + minCost(c, end)If no cut lies inside the segment, there's nothing to do and the cost is 0. This is the interval DP pattern: the state is a range, and you solve it by choosing a split point that carves it into two smaller ranges you've already solved. Because every sub-segment is defined by a pair of cut positions, there are only about m² distinct sub-problems — a world away from m!.
The optimal solution
Top-down recursion with memoization implements the recurrence directly. dfs(start, end) returns the minimum cost to make all cuts strictly between start and end, and a Map caches each result by its "start_end" key so no segment is ever recomputed.
var minCost = function (n, cuts) {
let dp = new Map();
let dfs = (start, end) => {
if (start >= end) return 0;
let key = start + "_" + end;
if (dp.has(key)) return dp.get(key);
let minCost = Infinity;
for (let c of cuts) {
if (c > start && c < end) {
let currCost = (end - start) +
dfs(start, c) + dfs(c, end);
minCost = Math.min(minCost, currCost);
}
}
minCost = minCost === Infinity ? 0 : minCost;
dp.set(key, minCost);
return minCost;
};
return dfs(0, n);
};A few details that matter:
- The boundaries
0andnare the stick's ends, so the top-level call isdfs(0, n)— no need to sort the input, since every candidate cut is filtered byc > start && c < end. minCoststarts atInfinity. If the loop never finds a cut inside the segment, thatInfinityis converted back to0before caching — an empty segment is free, not impossibly expensive.- The cache key is the exact
(start, end)pair. Because cut positions are distinct integers,"3_7"uniquely names one sub-stick, and every laterdfs(3, 7)returns instantly.
Walkthrough
Trace n = 7, cuts = [1, 3]. Each row is one dfs(start, end) call; the answer bubbles up from the leaves.
| Call | Cut tried c | Cost = (end−start) + dfs(start,c) + dfs(c,end) | Segment result |
|---|---|---|---|
dfs(0,1) | — (no cut inside) | 0 | 0 |
dfs(1,3) | — (no cut inside) | 0 | 0 |
dfs(3,7) | — (no cut inside) | 0 | 0 |
dfs(1,7) | 3 | (7−1) + dfs(1,3) + dfs(3,7) = 6 + 0 + 0 = 6 | 6 |
dfs(0,3) | 1 | (3−0) + dfs(0,1) + dfs(1,3) = 3 + 0 + 0 = 3 | 3 |
dfs(0,7) | 1 | (7−0) + dfs(0,1) + dfs(1,7) = 7 + 0 + 6 = 13 | candidate 13 |
dfs(0,7) | 3 | (7−0) + dfs(0,3) + dfs(3,7) = 7 + 3 + 0 = 10 | 10 ← min |
The top call dfs(0, 7) weighs its two choices of first cut. Cutting at 1 first strands a length-6 piece that still needs one more cut, costing 13. Cutting at 3 first splits the stick evenly enough that the leftover work is cheaper, landing at 10. The recursion never re-derives dfs(0,1) or dfs(1,3) — the second time each is needed, the memo returns it for free.
Complexity
Let m be the number of cuts.
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force (all orders) | O(m!) | O(m) | tries every permutation of cuts |
| Memoized interval DP | O(m³) | O(m²) | O(m²) distinct segments, each loops over O(m) cuts |
Every sub-problem is one pair of cut boundaries, so there are O(m²) of them. Solving one scans all m cuts to pick the best first cut, giving O(m³) total time. The memo stores one value per segment — O(m²) space — plus recursion depth up to O(m) on the call stack.
Common mistakes
- Being greedy about which cut to make first. Always cutting the middle, or the leftmost, seems reasonable but isn't optimal in general. Only trying every candidate first-cut per segment finds the true minimum.
- Forgetting the stick ends. The cost of a cut is measured against the current piece, whose left and right bounds are cut positions or
0andn. Drop the0/nboundaries and your segment lengths come out wrong. - Skipping memoization. The plain recursion is correct but exponential — it re-solves
dfs(3, 7)-style segments repeatedly. TheMapis what collapses O(m!) into O(m³). - Not converting
Infinityback to0. A segment with no interior cut must return0. Leaving it asInfinitypoisons every parent that adds it in. - Assuming input is sorted. The recurrence filters each cut with
c > start && c < end, so unsortedcutsstill works. (A bottom-up table version does need sorted boundaries — a different trade-off.)
Where this pattern shows up next
Interval DP and "combine two sub-ranges" recurrences recur across the hard-DP catalog:
- Palindromic Substrings — the other classic range-state DP, counting palindromes by expanding intervals.
- Longest Palindromic Substring — same interval reasoning, this time returning the longest range that stays valid.
- Decode Ways — one-dimensional DP where each state builds on the results of shorter prefixes.
- Maximum Subarray — the gentlest introduction to "carry the best answer forward" DP.
You can also step through Min Cost to Cut a Stick interactively to watch each segment resolve and the DP table fill in, one cut at a time.
FAQ
Why does the order of cuts change the total cost?
Because each cut costs the length of the piece it lands on, and pieces get shorter as you cut. If you cut a long stick early, that early cut is expensive but leaves shorter, cheaper pieces behind; cut it late and the same physical position may cost less. Since the set of cuts is fixed but the sequence is yours to choose, the total is minimized by an ordering that keeps expensive cuts off the longest pieces — which is exactly what the interval DP searches for.
What is the time and space complexity of the optimal solution?
Time is O(m³) and space is O(m²), where m is the number of cuts. Each sub-problem is defined by a pair of boundary positions, so there are O(m²) unique segments; solving one loops over all m candidate cuts to choose the cheapest first cut, multiplying to O(m³). The memo table holds one cached value per segment, giving O(m²) space, on top of a recursion stack up to O(m) deep.
Do I need to sort the cuts array first?
For the top-down memoized version shown here, no. Each recursive call filters candidates with c > start && c < end, so it only ever considers cuts that actually lie inside the current segment regardless of their order in the input array. Sorting becomes necessary only if you switch to a bottom-up table, where you iterate segments by increasing length and index into adjacent boundary positions — that indexing assumes the boundaries are in sorted order.
How is this different from a greedy approach?
A greedy rule picks one "obviously good" cut at each step — the middle, or the leftmost — and commits to it. That fails because the cheapest first cut for the whole stick depends on how the resulting pieces cut, which greedy never looks ahead to see. Interval DP instead tries every possible first cut for every segment and combines the optimal sub-results, guaranteeing the global minimum rather than a locally plausible guess.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.