Loading…

mediumDynamic ProgrammingFrequently asked

Rod Cutting

Q: How do you solve Rod Cutting using the Brute Force — Recursion Over the First Cut approach?

When to use it: Say this first to establish the first-cut recurrence, then flag the exponential branching before optimizing. Decide just the *first* piece. For a rod of remaining length `rem`, try every possible first-cut length `c` from `1` to `rem`: earn `price[c]`, then optimally cut the leftover `rem - c`. The best over all first cuts is the answer for `rem`. The base case is `best(0) = 0` — an empty rod earns nothing. **The mental shift: commit to one cut, recurse on the remainder.** You don't have to plan the whole set of cuts at once. Fix the length of the first piece, reduce the rod, and let recursion solve the smaller identical problem. Because any piece length stays available afterward, the subproblem faces the *same* price table — that's the unbounded (reusable-pieces) flavor. **Why c ranges over all of 1..rem.** Every composition of `rem` into ordered pieces is reachable by choosing different first cuts and recursing. We don't restrict `c` to 'larger than the last cut' because order of pieces doesn't change the total — we just want the best multiset, and scanning all first cuts finds it. **Why max of price.** The cuts are alternatives — we want the single best plan — so we combine with `max`. Leaving the rod whole is just the `c = rem` branch, automatically considered. **Why we don't ship this.** The same `rem` is recomputed across countless cut orderings — exponential overlap on one state variable. Cache `best(rem)` and the explosion collapses to O(n²). Time complexity: O(2ⁿ). Space complexity: O(n).

Q: How do you solve Rod Cutting using the Top-Down Memoization on Remaining Length approach?

When to use it: The fix once you name the overlap — 'cache the best price for each remaining length'. Keep the first-cut recurrence but cache `best(rem)` so each remaining length is solved exactly once. A `memo` array indexed by remaining length starts 'uncomputed'; on entry we return the cached value and store the result before returning. **The mental shift: the future depends only on the remaining length.** Two cut sequences that both leave a rod of length `rem` have identical optimal continuations, so caching by `rem` collapses all those duplicate explorations into one. The state space is just `0..n`, and since solving state `rem` scans up to `rem` first cuts, the total work is `0 + 1 + … + n = O(n²)`. **Why a 1-D memo is enough.** As in Coin Change and unbounded knapsack, the piece menu never shrinks (pieces are reusable), so the only state that matters is the remaining length. No item dimension is needed. **Why -1 as the sentinel.** A length-0 rod legitimately earns 0, so 0 can't double as 'uncomputed'. Initialize the memo to -1. **A language note.** This top-down form recurses up to `n` deep. For `n = 1000` Java is fine, but Python's default recursion limit is around 1000 — you'd be right at the edge and could hit `RecursionError`. That's the practical reason to prefer the bottom-up table in Python (next approach), which uses no recursion stack. Time complexity: O(n²). Space complexity: O(n).

Q: How do you solve Rod Cutting using the Bottom-Up — 1-D dp[] Table (Optimal) approach?

When to use it: The answer they want. Frame it as unbounded knapsack: 'fill dp[0..n]; dp[len] = max over c of price[c] + dp[len - c]'. Build the answers bottom-up. `dp[len]` is the maximum price for a rod of length `len`. Anchor `dp[0] = 0`, then for each length `len` from `1` to `n`, try every first-cut length `c` in `1..len` and relax `dp[len] = max(dp[len], price[c] + dp[len - c])`. The answer is `dp[n]`. **The mental shift: solve every shorter rod first.** Because `dp[len]` only reads `dp[len - c]` for positive `c`, processing lengths in increasing order guarantees every dependency is final by the time you need it. One clean sweep, no recursion. **Why this is unbounded knapsack.** Map the rod length to the knapsack capacity and a piece of length `c` to a reusable item of weight `c` and value `price[c]`. Then `dp[len] = max over items c of value[c] + dp[len - weight[c]]` is *literally* the unbounded knapsack recurrence. The 'reusable pieces' assumption is what lets `dp[len - c]` itself already contain pieces of length `c` — pieces repeat freely, exactly like coins in Coin Change. **Why no descending-vs-ascending worry here.** In the explicit 'for each length, scan all first cuts' formulation, `dp[len]` is computed in one shot from already-finalized shorter entries, so there's no rolling-array reuse hazard. If you instead wrote it knapsack-style (loop pieces outer, lengths inner over one array), you'd sweep length ascending — the unbounded direction — to allow reuse. **Why dp[0] = 0 anchors everything.** Every reachable length's best price chains back to `dp[0]` through a sequence of cuts. Leave it unset and nothing could be relaxed. Time complexity: O(n²). Space complexity: O(n).

Dynamic Programming · 23 of 44 · 10 min

You are given a rod of length n and an array price where price[i] is the price of a piece of length i (for i from 1 to n).

Cut the rod into one or more pieces (or leave it whole) to **maximize the total price** you can earn. You may cut as many pieces of any length as you like; equal-length pieces always earn the same price.

Return the maximum obtainable price.

In plain English

Partition a rod of length n into integer-length pieces so the summed prices are maximal, where a piece of length i is worth price[i] and any length may be cut any number of times. It is exactly unbounded knapsack: the rod length is the capacity, and each piece length is a reusable item whose weight equals its length and whose value is its price.

Examples

Example 1

Input: n = 4, price = [_, 1, 5, 8, 9] (length 1→1, 2→5, 3→8, 4→9)
Output: 10
Note: Cut into two length-2 pieces: 5 + 5 = 10. Beats one length-4 piece (9) and length 3 + 1 (8 + 1 = 9).

Example 2

Input: n = 8, price = [_, 1, 5, 8, 9, 10, 17, 17, 20]
Output: 22
Note: Cut into length 2 + length 6: 5 + 17 = 22. Better than one length-8 piece (20) or four length-2 (4×5 = 20).

Example 3

Input: n = 5, price = [_, 2, 5, 7, 8, 10]
Output: 12
Note: Cut length 2 + length 3: 5 + 7 = 12. Beats the whole length-5 piece (10).

Constraints

1 ≤ n ≤ 1000
1 ≤ price[i] ≤ 10⁵
price has a defined value for every length 1..n
All prices are positive integers

Clarifying questions5First question: Can I cut multiple pieces of the same length?Explore questions

Q1.Can I cut multiple pieces of the same length?
Yes — there's no limit on how many pieces of a given length you use. That makes it unbounded knapsack rather than 0/1.
Q2.How is the price array indexed?
price[i] is the price of a length-i piece. I'll treat price as 1-indexed by length (price[1] for length 1, etc.) to keep the recurrence clean.
Q3.Is leaving the rod uncut allowed?
Yes — one piece of length n is a valid 'cutting'. The loop's c = n case covers it, so no special handling is needed.
Q4.Can prices be non-monotonic in length?
Yes — a length-2 piece can be worth more or less than two length-1 pieces. That's the whole point: you can't assume bigger is better.
Q5.What's the answer for n = 0?
0 — there's nothing to cut. That's the base case dp[0] = 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Given a rod of length n and a price table where price[i] is the value of a piece of length i, cut the rod to maximize total price. The recurrence is dp[len] = max over first-cut c in 1..len of price[c] + dp[len - c]. It's unbounded knapsack: a length-c piece is a reusable item of weight c and value price[c]. Naive recursion is exponential; memoize on remaining length or build a 1-D dp[] table in O(n²).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize a value-maximizing partition as unbounded knapsack, set up the first-cut recurrence, and keep the price-table indexing straight.

Where candidates slip

Off-by-one indexing of the price table (treating price[i] as length i+1 or vice versa), or shrinking the available piece sizes as if pieces were single-use.

How to stand out

Say out loud 'this is unbounded knapsack — length is the capacity, a length-c piece is a reusable item worth price[c]'. Derive dp[len] = max over c of price[c] + dp[len-c], then give the O(n²) table.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion Over the First Cut	`O(2ⁿ)`	`O(n)`	Say this first to establish the first-cut recurrence, then flag the exponential branching before optimizing.	Read
2	Top-Down Memoization on Remaining Length	`O(n²)`	`O(n)`	The fix once you name the overlap — 'cache the best price for each remaining length'.	Read
3	Bottom-Up — 1-D dp[] Table (Optimal)Optimal	`O(n²)`	`O(n)`	The answer they want. Frame it as unbounded knapsack: 'fill dp[0..n]; dp[len] = max over c of price[c] + dp[len - c]'.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewCut rod to maximize pricePieces reusable or once each?Once eachReusableExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion Over the First Cut

TimeO(2ⁿ)SpaceO(n)

Say this first to establish the first-cut recurrence, then flag the exponential branching before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Decide only the FIRST piece you cut off. If it has length c, what's left to solve?

2Hint 2Explore hint

Cutting a first piece of length c (1 ≤ c ≤ rem) earns price[c] and leaves a rod of length rem - c to cut optimally.

3Hint 3Explore hint

best(rem) = max over c in 1..rem of price[c] + best(rem - c), with best(0) = 0.

A · Core idea

Decide just the first piece. For a rod of remaining length rem, try every possible first-cut length c from 1 to rem: earn price[c], then optimally cut the leftover rem - c. The best over all first cuts is the answer for rem. The base case is best(0) = 0 — an empty rod earns nothing.

The mental shift: commit to one cut, recurse on the remainder. You don't have to plan the whole set of cuts at once. Fix the length of the first piece, reduce the rod, and let recursion solve the smaller identical problem. Because any piece length stays available afterward, the subproblem faces the same price table — that's the unbounded (reusable-pieces) flavor.

Why c ranges over all of 1..rem. Every composition of rem into ordered pieces is reachable by choosing different first cuts and recursing. We don't restrict c to 'larger than the last cut' because order of pieces doesn't change the total — we just want the best multiset, and scanning all first cuts finds it.

Why max of price. The cuts are alternatives — we want the single best plan — so we combine with max. Leaving the rod whole is just the c = rem branch, automatically considered.

Why we don't ship this. The same rem is recomputed across countless cut orderings — exponential overlap on one state variable. Cache best(rem) and the explosion collapses to O(n²).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4, price[1..4] = [1, 5, 8, 9]

best(4)

c=1→1+best(3); c=2→5+best(2); c=3→8+best(1); c=4→9+best(0)

Statebranches out

Final result10

C · Code with teaching comments

Reference implementation previewpublic int rodCutting(int[] price, int n) { return best(price, n); } // price is 1-indexed: price[c] is the value of a length-c pieceExplore the full code

solution.javaJava

Brute Force — Recursion Over the First Cut — reference

3 teaching notes

1
public int rodCutting(int[] price, int n) {
2
    return best(price, n);
3
}
4
 
5
// price is 1-indexed: price[c] is the value of a length-c piece
6
private int best(int[] price, int rem) {
7
    // Base case: an empty rod earns 0 — every cutting bottoms out here.
8
    if (rem == 0) {
9
        return 0;
10
    }
11
    int top = 0;
12
    // Try every first-cut length from 1 up to the whole remaining rod.
13
    for (int c = 1; c <= rem; c++) {
14
        // Earn price[c] for the first piece, then optimally cut the rest. c = rem
15
        // covers 'leave it whole'.
16
        top = Math.max(top, price[c] + best(price, rem - c));
17
    }
18
    return top;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

The recurrence depends on a single number — the remaining length — yet the naive tree re-solves best(rem) for the same rem repeatedly through different first cuts. One state variable plus heavy overlap is the textbook signal for an O(n²) DP.

ComplexityO(2ⁿ) time, O(n) space — Each call branches into up to `rem` recursive calls and the recursion can be `n` deep, producing exponential 2ⁿ nodes (each length can be split in 2^(len-1) compositions). Stack depth is O(n).

E · Edge cases and pitfalls4n = 0 — best(0) = 0 immediately — nothing to cut.Explore edge cases

Edge cases handled

n = 0best(0) = 0 immediately — nothing to cut.

Pitfalls

Off-by-one in the price index — price[c] must be the value of a length-c piece.
Restricting c to avoid 'repeats' — pieces are reusable, so every length 1..rem is fair game.
Skipping this approach — the first-cut recurrence is exactly what you should verbalize before optimizing.

03.2

Approach 2 of 3

Top-Down Memoization on Remaining Length

TimeO(n²)SpaceO(n)

The fix once you name the overlap — 'cache the best price for each remaining length'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

best(rem) yields the same value every call. Where can you store it so each length is solved once?

2Hint 2Explore hint

Add a memo of size n+1 indexed by remaining length. Check on entry, fill before returning.

3Hint 3Explore hint

memo[rem] = max over c of price[c] + best(rem - c); use -1 for 'uncomputed' since 0 is a valid (empty-rod) answer.

A · Core idea

Keep the first-cut recurrence but cache best(rem) so each remaining length is solved exactly once. A memo array indexed by remaining length starts 'uncomputed'; on entry we return the cached value and store the result before returning.

The mental shift: the future depends only on the remaining length. Two cut sequences that both leave a rod of length rem have identical optimal continuations, so caching by rem collapses all those duplicate explorations into one. The state space is just 0..n, and since solving state rem scans up to rem first cuts, the total work is 0 + 1 + … + n = O(n²).

Why a 1-D memo is enough. As in Coin Change and unbounded knapsack, the piece menu never shrinks (pieces are reusable), so the only state that matters is the remaining length. No item dimension is needed.

Why -1 as the sentinel. A length-0 rod legitimately earns 0, so 0 can't double as 'uncomputed'. Initialize the memo to -1.

A language note. This top-down form recurses up to n deep. For n = 1000 Java is fine, but Python's default recursion limit is around 1000 — you'd be right at the edge and could hit RecursionError. That's the practical reason to prefer the bottom-up table in Python (next approach), which uses no recursion stack.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 8, price[1..8] = [1, 5, 8, 9, 10, 17, 17, 20]

best(8)

scans c=1..8, needs best(7..0)

Statememo empty

Final result22

C · Code with teaching comments

Reference implementation previewpublic int rodCutting(int[] price, int n) { int[] memo = new int[n + 1]; Arrays.fill(memo, -1); return best(price, n, memo); }Explore the full code

solution.javaJava

Top-Down Memoization on Remaining Length — reference

4 teaching notes

1
public int rodCutting(int[] price, int n) {
2
    int[] memo = new int[n + 1];
3
    // -1 marks 'uncomputed' — distinct from the valid 0 earned by an empty rod.
4
    Arrays.fill(memo, -1);
5
    return best(price, n, memo);
6
}
7
 
8
private int best(int[] price, int rem, int[] memo) {
9
    if (rem == 0) {
10
        return 0;
11
    }
12
    // Cache hit — return the stored best price for this length in O(1).
13
    if (memo[rem] != -1) {
14
        return memo[rem];
15
    }
16
    int top = 0;
17
    for (int c = 1; c <= rem; c++) {
18
        // Try each first cut; the recursion keeps every piece length available (reuse).
19
        top = Math.max(top, price[c] + best(price, rem - c, memo));
20
    }
21
    // Store the resolved best before returning so this length is never recomputed.
22
    memo[rem] = top;
23
    return top;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

This is the same mechanical upgrade as every DP: a correct recurrence plus a cache keyed on the true state (the remaining length). Recognizing that remaining length alone determines the future — because pieces repeat — is the whole insight; the cache then writes itself.

ComplexityO(n²) time, O(n) space — There are n+1 distinct remaining-length states. State `rem` does O(rem) work scanning first cuts, and summed over all states that's O(n²). Memo plus recursion stack is O(n).

E · Edge cases and pitfalls5n = 0 — best(0) = 0 immediately.Explore edge cases

Edge cases handled

n = 0best(0) = 0 immediately.
n = 1Only c = 1 possible → price[1].

Pitfalls

Using 0 as 'uncomputed' — collides with the empty-rod value 0; use -1.
Sizing the memo as n instead of n+1 — lengths 0..n need n+1 slots.
Recursing to depth n in Python can hit the ~1000 recursion limit for large n — tabulation avoids the stack.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — 1-D dp[] Table (Optimal)

TimeO(n²)SpaceO(n)

The answer they want. Frame it as unbounded knapsack: 'fill dp[0..n]; dp[len] = max over c of price[c] + dp[len - c]'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Compute the best price for a rod of length 1, then 2, ... up to n, reusing earlier answers.

2Hint 2Explore hint

dp[len] = best price for a rod of length len. dp[0] = 0. For each len, try every first cut c in 1..len.

3Hint 3Explore hint

dp[len] = max(dp[len], price[c] + dp[len - c]). Because dp[len - c] is already final and pieces repeat, no special loop direction is needed — but think of it as the ascending unbounded sweep.

A · Core idea

Build the answers bottom-up. dp[len] is the maximum price for a rod of length len. Anchor dp[0] = 0, then for each length len from 1 to n, try every first-cut length c in 1..len and relax dp[len] = max(dp[len], price[c] + dp[len - c]). The answer is dp[n].

The mental shift: solve every shorter rod first. Because dp[len] only reads dp[len - c] for positive c, processing lengths in increasing order guarantees every dependency is final by the time you need it. One clean sweep, no recursion.

Why this is unbounded knapsack. Map the rod length to the knapsack capacity and a piece of length c to a reusable item of weight c and value price[c]. Then dp[len] = max over items c of value[c] + dp[len - weight[c]] is literally the unbounded knapsack recurrence. The 'reusable pieces' assumption is what lets dp[len - c] itself already contain pieces of length c — pieces repeat freely, exactly like coins in Coin Change.

Why no descending-vs-ascending worry here. In the explicit 'for each length, scan all first cuts' formulation, dp[len] is computed in one shot from already-finalized shorter entries, so there's no rolling-array reuse hazard. If you instead wrote it knapsack-style (loop pieces outer, lengths inner over one array), you'd sweep length ascending — the unbounded direction — to allow reuse.

Why dp[0] = 0 anchors everything. Every reachable length's best price chains back to dp[0] through a sequence of cuts. Leave it unset and nothing could be relaxed.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4, price[1..4] = [1, 5, 8, 9]

Array state

init

dp[0]=0, rest 0

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result10

C · Code with teaching comments

solution.javaJava

Bottom-Up — 1-D dp[] Table (Optimal) — optimal

4 teaching notes

1
public int rodCutting(int[] price, int n) {
2
    // dp[len] = best price for a length-len rod; dp[0] defaults to 0, the anchor.
3
    int[] dp = new int[n + 1];
4
    // Solve shorter rods first so every dp[len - c] is already final.
5
    for (int len = 1; len <= n; len++) {
6
        // Try every first-cut length; c = len is the 'leave it whole' option.
7
        for (int c = 1; c <= len; c++) {
8
            // Earn price[c] for the first piece plus the optimal price of the
9
            // remainder. The whole DP in one line.
10
            dp[len] = Math.max(dp[len], price[c] + dp[len - c]);
11
        }
12
    }
13
    return dp[n];
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

Rod Cutting is unbounded knapsack with capacity = rod length and item c = a length-c piece worth price[c]. The same engine, relabeled, also gives Coin Change (min count) and Integer Break. Once you see the mapping, you never re-derive it — you recognize it.

ComplexityO(n²) time, O(n) space — Outer loop runs n times; the inner first-cut loop runs up to len times, summing to O(n²). A single dp array of size n+1 → O(n) space, no recursion stack.

E · Edge cases and pitfalls6n = 0 — Outer loop never runs; dp[0] = 0 returned.Explore edge cases

Edge cases handled

n = 0Outer loop never runs; dp[0] = 0 returned.
price[1] dominatesIf length-1 has the best price-per-length, dp[n] = n × price[1] (all unit cuts).
whole rod bestIf price[n] beats every split, the c = n branch makes dp[n] = price[n].

Pitfalls

Misaligning the price index — price[c] must be the value of a length-c piece, not length c-1 or c+1.
Treating pieces as single-use (0/1) — Rod Cutting allows repeating any length.
Building a 2-D table when the 1-D table already captures the reusable-piece state.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewpublic int rodCutting(int[] price, int n) { int[] dp = new int[n + 1]; for (int len = 1; len <= n; len++) { for (int c = 1; c <= len; c++) { dp[len] = Math.max(dp[len], price[c] + dp[len - c]);Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Price-array off-by-one

If price is given 0-indexed (price[0] = value of length 1), but you index price[c] expecting length c, every piece value is shifted. Decide the indexing up front and keep it consistent.

Explore the code comparison

Don't write this

# price 0-indexed: price[0] is length-1 value
for c in range(1, length + 1):
    dp[length] = max(dp[length], price[c] + dp[length - c])  # price[c] is length c+1!

Write this instead

# price 0-indexed: price[i] is length-(i+1) value
for c in range(1, length + 1):
    dp[length] = max(dp[length], price[c - 1] + dp[length - c])

Treating pieces as single-use

Rod Cutting lets you cut as many pieces of a length as you want. Coding it as 0/1 (each length once) undercounts — you'd miss answers like 'two length-2 pieces'.

Explore the code comparison

Don't write this

// 0/1 style: each length considered once, descending
for (int c = 1; c <= n; c++)
    for (int len = n; len >= c; len--)
        dp[len] = Math.max(dp[len], price[c] + dp[len - c]);

Write this instead

// unbounded: lengths reusable
for (int len = 1; len <= n; len++)
    for (int c = 1; c <= len; c++)
        dp[len] = Math.max(dp[len], price[c] + dp[len - c]);

Wrong base / sentinel handling in memo

An empty rod earns 0, so 0 cannot mean 'uncomputed' in the memo. Use -1, or you'll treat already-solved zero-length states as unsolved.

Explore the code comparison

Don't write this

int[] memo = new int[n + 1]; // all 0
if (memo[rem] != 0) return memo[rem];

Write this instead

int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
if (memo[rem] != -1) return memo[rem];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Rod cutting — unbounded knapsack over piece lengths

Code pattern to memorize

dp[0] = 0
for len in 1..n:
    for c in 1..len:
        dp[len] = max(dp[len], price[c] + dp[len - c])
return dp[n]

Rules to remember

1The 'first cut' c ranges over 1..len; you collect price[c] and recurse on the remaining len - c.
2Pieces are reusable — you may cut several pieces of the same length, so it's unbounded knapsack, not 0/1.
3Index carefully: price[i] is the value of a length-i piece. If the table is 0-indexed with price[0] unused (or absent), align it so price[c] is the price of length c.
4Anchor dp[0] = 0 — a length-0 rod earns nothing — and the answer is dp[n].
5No 'leave it whole' special case is needed: choosing c = len (one piece) is already covered by the loop.

Use this pattern when

Maximize value by partitioning a length/quantity into reusable pieces from a value table
Every position can be a cut point; pieces of equal length have equal value
Repetition of piece sizes is allowed and order of pieces doesn't matter
Problem reads as 'unbounded knapsack with capacity = length, item i = weight i / value price[i]'

Choose another pattern when

Each piece length usable at most once → 0/1 knapsack, descending sweep
You want the number of distinct cut patterns → counting DP, not max-value
Cuts have positional costs depending on where you cut (not just length) → interval DP like Matrix Chain / Burst Balloons
Lengths are huge with a tiny price table → O(n²) infeasible, rethink

Interview takeaway

Rod Cutting is unbounded knapsack wearing a different costume: capacity = rod length, item of weight c = a piece of length c worth price[c]. The recurrence dp[len] = max over c of price[c] + dp[len - c] is the same skeleton as Coin Change. Once you map 'cut a first piece, recurse on the rest', the O(n²) table is automatic.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical unbounded-knapsack relabeling. Recognize Rod Cutting whenever you partition a length/quantity into reusable pieces drawn from a value table, maximizing total value. The recurrence dp[len] = max over c of price[c] + dp[len - c] is identical in shape to Coin Change and the generic unbounded knapsack.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Unbounded Knapsack
Rod Cutting is exactly this with weight[c] = c and value[c] = price[c]. Generalize to arbitrary item weights.
Coin Change
Same reusable-item DP but minimizing the count of pieces to hit an exact target instead of maximizing price.
Integer Break
Coming soon
Cut n into a sum of integers to maximize their PRODUCT — same first-split recurrence, product objective.
Rod Cutting with Cut Cost
Coming soon
Subtract a fixed cost per cut — add a penalty term to each split branch, turning it into a net-value DP.

Same pattern

←

Matrix Chain Multiplication

Continue · Next problem

Subset Sum

mediumDynamic ProgrammingFrequently asked

Rod Cutting

Dynamic Programming · 23 of 44 · 10 min

You are given a rod of length n and an array price where price[i] is the price of a piece of length i (for i from 1 to n).

Return the maximum obtainable price.

In plain English

Examples

Example 1

Input: n = 4, price = [_, 1, 5, 8, 9] (length 1→1, 2→5, 3→8, 4→9)
Output: 10
Note: Cut into two length-2 pieces: 5 + 5 = 10. Beats one length-4 piece (9) and length 3 + 1 (8 + 1 = 9).

Example 2

Input: n = 8, price = [_, 1, 5, 8, 9, 10, 17, 17, 20]
Output: 22
Note: Cut into length 2 + length 6: 5 + 17 = 22. Better than one length-8 piece (20) or four length-2 (4×5 = 20).

Example 3

Input: n = 5, price = [_, 2, 5, 7, 8, 10]
Output: 12
Note: Cut length 2 + length 3: 5 + 7 = 12. Beats the whole length-5 piece (10).

Constraints

1 ≤ n ≤ 1000
1 ≤ price[i] ≤ 10⁵
price has a defined value for every length 1..n
All prices are positive integers

Clarifying questions5First question: Can I cut multiple pieces of the same length?Explore questions

Q1.Can I cut multiple pieces of the same length?
Yes — there's no limit on how many pieces of a given length you use. That makes it unbounded knapsack rather than 0/1.
Q2.How is the price array indexed?
price[i] is the price of a length-i piece. I'll treat price as 1-indexed by length (price[1] for length 1, etc.) to keep the recurrence clean.
Q3.Is leaving the rod uncut allowed?
Yes — one piece of length n is a valid 'cutting'. The loop's c = n case covers it, so no special handling is needed.
Q4.Can prices be non-monotonic in length?
Yes — a length-2 piece can be worth more or less than two length-1 pieces. That's the whole point: you can't assume bigger is better.
Q5.What's the answer for n = 0?
0 — there's nothing to cut. That's the base case dp[0] = 0.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you recognize a value-maximizing partition as unbounded knapsack, set up the first-cut recurrence, and keep the price-table indexing straight.

Where candidates slip

Off-by-one indexing of the price table (treating price[i] as length i+1 or vice versa), or shrinking the available piece sizes as if pieces were single-use.

How to stand out

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Brute Force — Recursion Over the First Cut	`O(2ⁿ)`	`O(n)`	Say this first to establish the first-cut recurrence, then flag the exponential branching before optimizing.	Read
2	Top-Down Memoization on Remaining Length	`O(n²)`	`O(n)`	The fix once you name the overlap — 'cache the best price for each remaining length'.	Read
3	Bottom-Up — 1-D dp[] Table (Optimal)Optimal	`O(n²)`	`O(n)`	The answer they want. Frame it as unbounded knapsack: 'fill dp[0..n]; dp[len] = max over c of price[c] + dp[len - c]'.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 3

Brute Force — Recursion Over the First Cut

TimeO(2ⁿ)SpaceO(n)

Say this first to establish the first-cut recurrence, then flag the exponential branching before optimizing.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Decide only the FIRST piece you cut off. If it has length c, what's left to solve?

2Hint 2Explore hint

Cutting a first piece of length c (1 ≤ c ≤ rem) earns price[c] and leaves a rod of length rem - c to cut optimally.

3Hint 3Explore hint

best(rem) = max over c in 1..rem of price[c] + best(rem - c), with best(0) = 0.

A · Core idea

Why max of price. The cuts are alternatives — we want the single best plan — so we combine with max. Leaving the rod whole is just the c = rem branch, automatically considered.

Why we don't ship this. The same rem is recomputed across countless cut orderings — exponential overlap on one state variable. Cache best(rem) and the explosion collapses to O(n²).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4, price[1..4] = [1, 5, 8, 9]

best(4)

c=1→1+best(3); c=2→5+best(2); c=3→8+best(1); c=4→9+best(0)

Statebranches out

Final result10

C · Code with teaching comments

Reference implementation previewpublic int rodCutting(int[] price, int n) { return best(price, n); } // price is 1-indexed: price[c] is the value of a length-c pieceExplore the full code

solution.javaJava

Brute Force — Recursion Over the First Cut — reference

3 teaching notes

1
public int rodCutting(int[] price, int n) {
2
    return best(price, n);
3
}
4
 
5
// price is 1-indexed: price[c] is the value of a length-c piece
6
private int best(int[] price, int rem) {
7
    // Base case: an empty rod earns 0 — every cutting bottoms out here.
8
    if (rem == 0) {
9
        return 0;
10
    }
11
    int top = 0;
12
    // Try every first-cut length from 1 up to the whole remaining rod.
13
    for (int c = 1; c <= rem; c++) {
14
        // Earn price[c] for the first piece, then optimally cut the rest. c = rem
15
        // covers 'leave it whole'.
16
        top = Math.max(top, price[c] + best(price, rem - c));
17
    }
18
    return top;
19
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.19 lines

D · Why it works and complexityO(2ⁿ) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls4n = 0 — best(0) = 0 immediately — nothing to cut.Explore edge cases

Edge cases handled

n = 0best(0) = 0 immediately — nothing to cut.

Pitfalls

Off-by-one in the price index — price[c] must be the value of a length-c piece.
Restricting c to avoid 'repeats' — pieces are reusable, so every length 1..rem is fair game.
Skipping this approach — the first-cut recurrence is exactly what you should verbalize before optimizing.

03.2

Approach 2 of 3

Top-Down Memoization on Remaining Length

TimeO(n²)SpaceO(n)

The fix once you name the overlap — 'cache the best price for each remaining length'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

best(rem) yields the same value every call. Where can you store it so each length is solved once?

2Hint 2Explore hint

Add a memo of size n+1 indexed by remaining length. Check on entry, fill before returning.

3Hint 3Explore hint

memo[rem] = max over c of price[c] + best(rem - c); use -1 for 'uncomputed' since 0 is a valid (empty-rod) answer.

A · Core idea

Why -1 as the sentinel. A length-0 rod legitimately earns 0, so 0 can't double as 'uncomputed'. Initialize the memo to -1.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 8, price[1..8] = [1, 5, 8, 9, 10, 17, 17, 20]

best(8)

scans c=1..8, needs best(7..0)

Statememo empty

Final result22

C · Code with teaching comments

Reference implementation previewpublic int rodCutting(int[] price, int n) { int[] memo = new int[n + 1]; Arrays.fill(memo, -1); return best(price, n, memo); }Explore the full code

solution.javaJava

Top-Down Memoization on Remaining Length — reference

4 teaching notes

1
public int rodCutting(int[] price, int n) {
2
    int[] memo = new int[n + 1];
3
    // -1 marks 'uncomputed' — distinct from the valid 0 earned by an empty rod.
4
    Arrays.fill(memo, -1);
5
    return best(price, n, memo);
6
}
7
 
8
private int best(int[] price, int rem, int[] memo) {
9
    if (rem == 0) {
10
        return 0;
11
    }
12
    // Cache hit — return the stored best price for this length in O(1).
13
    if (memo[rem] != -1) {
14
        return memo[rem];
15
    }
16
    int top = 0;
17
    for (int c = 1; c <= rem; c++) {
18
        // Try each first cut; the recursion keeps every piece length available (reuse).
19
        top = Math.max(top, price[c] + best(price, rem - c, memo));
20
    }
21
    // Store the resolved best before returning so this length is never recomputed.
22
    memo[rem] = top;
23
    return top;
24
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.24 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

E · Edge cases and pitfalls5n = 0 — best(0) = 0 immediately.Explore edge cases

Edge cases handled

n = 0best(0) = 0 immediately.
n = 1Only c = 1 possible → price[1].

Pitfalls

Using 0 as 'uncomputed' — collides with the empty-rod value 0; use -1.
Sizing the memo as n instead of n+1 — lengths 0..n need n+1 slots.
Recursing to depth n in Python can hit the ~1000 recursion limit for large n — tabulation avoids the stack.

03.3

Approach 3 of 3 · Optimal

Bottom-Up — 1-D dp[] Table (Optimal)

TimeO(n²)SpaceO(n)

The answer they want. Frame it as unbounded knapsack: 'fill dp[0..n]; dp[len] = max over c of price[c] + dp[len - c]'.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

Compute the best price for a rod of length 1, then 2, ... up to n, reusing earlier answers.

2Hint 2Explore hint

dp[len] = best price for a rod of length len. dp[0] = 0. For each len, try every first cut c in 1..len.

3Hint 3Explore hint

dp[len] = max(dp[len], price[c] + dp[len - c]). Because dp[len - c] is already final and pieces repeat, no special loop direction is needed — but think of it as the ascending unbounded sweep.

A · Core idea

Why dp[0] = 0 anchors everything. Every reachable length's best price chains back to dp[0] through a sequence of cuts. Leave it unset and nothing could be relaxed.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

n = 4, price[1..4] = [1, 5, 8, 9]

Array state

init

dp[0]=0, rest 0

[0]

[1]

[2]

[3]

[4]

Current pointerResolved stateNot processed

Final result10

C · Code with teaching comments

solution.javaJava

Bottom-Up — 1-D dp[] Table (Optimal) — optimal

4 teaching notes

1
public int rodCutting(int[] price, int n) {
2
    // dp[len] = best price for a length-len rod; dp[0] defaults to 0, the anchor.
3
    int[] dp = new int[n + 1];
4
    // Solve shorter rods first so every dp[len - c] is already final.
5
    for (int len = 1; len <= n; len++) {
6
        // Try every first-cut length; c = len is the 'leave it whole' option.
7
        for (int c = 1; c <= len; c++) {
8
            // Earn price[c] for the first piece plus the optimal price of the
9
            // remainder. The whole DP in one line.
10
            dp[len] = Math.max(dp[len], price[c] + dp[len - c]);
11
        }
12
    }
13
    return dp[n];
14
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.14 lines

D · Why it works and complexityO(n²) timeO(n) spaceOpen the invariant and proofExplore the proof

ComplexityO(n²) time, O(n) space — Outer loop runs n times; the inner first-cut loop runs up to len times, summing to O(n²). A single dp array of size n+1 → O(n) space, no recursion stack.

E · Edge cases and pitfalls6n = 0 — Outer loop never runs; dp[0] = 0 returned.Explore edge cases

Edge cases handled

n = 0Outer loop never runs; dp[0] = 0 returned.
price[1] dominatesIf length-1 has the best price-per-length, dp[n] = n × price[1] (all unit cuts).
whole rod bestIf price[n] beats every split, the c = n branch makes dp[n] = price[n].

Pitfalls

Misaligning the price index — price[c] must be the value of a length-c piece, not length c-1 or c+1.
Treating pieces as single-use (0/1) — Rod Cutting allows repeating any length.
Building a 2-D table when the 1-D table already captures the reusable-piece state.

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Price-array off-by-one

If price is given 0-indexed (price[0] = value of length 1), but you index price[c] expecting length c, every piece value is shifted. Decide the indexing up front and keep it consistent.

Explore the code comparison

Don't write this

# price 0-indexed: price[0] is length-1 value
for c in range(1, length + 1):
    dp[length] = max(dp[length], price[c] + dp[length - c])  # price[c] is length c+1!

Write this instead

# price 0-indexed: price[i] is length-(i+1) value
for c in range(1, length + 1):
    dp[length] = max(dp[length], price[c - 1] + dp[length - c])

Treating pieces as single-use

Rod Cutting lets you cut as many pieces of a length as you want. Coding it as 0/1 (each length once) undercounts — you'd miss answers like 'two length-2 pieces'.

Explore the code comparison

Don't write this

// 0/1 style: each length considered once, descending
for (int c = 1; c <= n; c++)
    for (int len = n; len >= c; len--)
        dp[len] = Math.max(dp[len], price[c] + dp[len - c]);

Write this instead

// unbounded: lengths reusable
for (int len = 1; len <= n; len++)
    for (int c = 1; c <= len; c++)
        dp[len] = Math.max(dp[len], price[c] + dp[len - c]);

Wrong base / sentinel handling in memo

An empty rod earns 0, so 0 cannot mean 'uncomputed' in the memo. Use -1, or you'll treat already-solved zero-length states as unsolved.

Explore the code comparison

Don't write this

int[] memo = new int[n + 1]; // all 0
if (memo[rem] != 0) return memo[rem];

Write this instead

int[] memo = new int[n + 1];
Arrays.fill(memo, -1);
if (memo[rem] != -1) return memo[rem];

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Rod cutting — unbounded knapsack over piece lengths

Code pattern to memorize

dp[0] = 0
for len in 1..n:
    for c in 1..len:
        dp[len] = max(dp[len], price[c] + dp[len - c])
return dp[n]

Rules to remember

1The 'first cut' c ranges over 1..len; you collect price[c] and recurse on the remaining len - c.
2Pieces are reusable — you may cut several pieces of the same length, so it's unbounded knapsack, not 0/1.
3Index carefully: price[i] is the value of a length-i piece. If the table is 0-indexed with price[0] unused (or absent), align it so price[c] is the price of length c.
4Anchor dp[0] = 0 — a length-0 rod earns nothing — and the answer is dp[n].
5No 'leave it whole' special case is needed: choosing c = len (one piece) is already covered by the loop.

Use this pattern when

Maximize value by partitioning a length/quantity into reusable pieces from a value table
Every position can be a cut point; pieces of equal length have equal value
Repetition of piece sizes is allowed and order of pieces doesn't matter
Problem reads as 'unbounded knapsack with capacity = length, item i = weight i / value price[i]'

Choose another pattern when

Each piece length usable at most once → 0/1 knapsack, descending sweep
You want the number of distinct cut patterns → counting DP, not max-value
Cuts have positional costs depending on where you cut (not just length) → interval DP like Matrix Chain / Burst Balloons
Lengths are huge with a tiny price table → O(n²) infeasible, rethink

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Unbounded Knapsack
Rod Cutting is exactly this with weight[c] = c and value[c] = price[c]. Generalize to arbitrary item weights.
Coin Change
Same reusable-item DP but minimizing the count of pieces to hit an exact target instead of maximizing price.
Integer Break
Coming soon
Cut n into a sum of integers to maximize their PRODUCT — same first-split recurrence, product objective.
Rod Cutting with Cut Cost
Coming soon
Subtract a fixed cost per cut — add a penalty term to each split branch, turning it into a net-value DP.

Same pattern

←

Matrix Chain Multiplication

Continue · Next problem

Subset Sum