The idea: sell the rod in the best pieces

A shop buys long steel rods and sells them cut into pieces of whole inches. A piece of length i sells for the price p[i], and prices are not proportional to length. Given a rod of length n, which cuts earn the most? This is the rod-cutting problem from CLRS §15.1. With the CLRS prices 1, 5, 8, 9 for lengths 1 to 4, a rod of length 4 earns 9 uncut but 10 as two pieces of length 2.

The 8 ways to cut a rod of length 4 with prices 1, 5, 8, 9: uncut 9, 1+3 and 3+1 earn 9, 2+2 earns 10, 1+1+2 in three orders earn 7, 1+1+1+1 earns 4. 2+2 is the best
A rod of length 4 can be cut in 2³ = 8 ways; two pieces of length 2 earn the most, 10.

Each of the n − 1 inch marks is either cut or not, so there are 2n−1 plans. Trying them all is hopeless for long rods, but the plans share their tails, and that is what dynamic programming uses.

The recurrence: first piece plus the best rest

Let r[j] be the most money a rod of length j can bring. Any plan for length j starts with a first piece of some length i (1 ≤ i ≤ j; i = j means no cut). What follows is a rod of length j − i, and in a best plan it must itself be sold the best way, or swapping in a better plan for it would earn more. This is optimal substructure:

r[0] = 0
r[j] = max over 1 ≤ i ≤ j of  p[i] + r[j − i]
cut[j] = the i that gives the max      (ties keep the smallest i)

In the animation the trial rod shows one candidate at a time: the first piece in orange with its price p[i], the rest in blue with r[j − i], read from the table. The side panel lists every candidate and marks the best. (Demo: CLRS prices, n = 4.)

Bottom-up: fill r[0], r[1], …, r[n]

r[j] only reads r[0..j − 1], so filling the row left to right never reads an empty cell. That is CLRS BOTTOM-UP-CUT-ROD; the version that also writes cut[j] is EXTENDED-BOTTOM-UP-CUT-ROD.

r[0] = 0
for j = 1 to n
    best = −∞
    for i = 1 to j
        if p[i] + r[j − i] > best
            best = p[i] + r[j − i];  cut[j] = i
    r[j] = best

With the CLRS prices the row is:

j012345678910
p[j]–1589101717202430
r[j]015810131718222530
cut[j]–12322612310

Rebuilding the cuts from cut[]

r[n] is only the money. To get the pieces, read cut[n]: that is the first piece. Cut it off, and the rest has length n − cut[n], whose first piece is cut[n − cut[n]], and so on until nothing is left. The animation does this on the real rod: each piece appears over the rod, then moves to the pieces row.

The r and cut rows for the CLRS prices up to length 8. Starting at cut[8] = 2 gives a piece of length 2; the rest is 6, and cut[6] = 6 gives one piece of length 6; the rod is sold as 2 + 6 for 5 + 17 = 22
For n = 8: cut[8] = 2, then cut[6] = 6, so the rod is sold as 2 + 6 for 5 + 17 = 22.

Demo: CLRS prices, n = 7 has a tie: 1 + 6 and 2 + 2 + 3 both earn 18. The strict ">" keeps the first candidate, i = 1, so the page shows 1 + 6. Demo: n = 10 ends with cut[10] = 10: the uncut rod, worth 30, beats every cut.

Greedy by price per inch fails

A natural shortcut is to cut first the piece with the best density p[i] / i, then repeat on the rest. With the CLRS prices and n = 4 the best density is length 3 (8 / 3 ≈ 2.67), so greedy sells 3 + 1 for 9, not 10. Demo: greedy by price per inch fails makes the gap bigger: prices 1, 2, 15, 21, 22, 24 and n = 6. Length 4 has the best density (21 / 4 = 5.25), but it leaves 2 inches worth only 2, so greedy gets 23 while 3 + 3 earns 30. Grabbing the best-looking piece can spoil the rest, so every first piece has to be tried.

The unbounded-knapsack pattern

Rod cutting is an unbounded knapsack: the rod length is the capacity, a piece of length i is an item of weight i and value p[i], and each piece length can be used any number of times. The table is one row indexed by capacity, and each cell tries every item as "the first one". The 0/1 knapsack differs only in that each item is used at most once, which needs a second index for "items considered so far". Coin change is the same pattern with coins instead of pieces.

problemcapacityitemseach itemcell
rod cuttingrod length jpiece lengths 1..nany number of timesmax p[i] + r[j − i]
unbounded knapsackweight witemsany number of timesmax vi + best[w − wi]
0/1 knapsackweight witems 1..iat most oncemax of skip, vi + best[i − 1][w − wi]

Running time

Filling r[j] checks j candidates, so the whole row needs 1 + 2 + … + n = n(n + 1)/2 checks: Θ(n²) time and Θ(n) space for r[] and cut[]. For n = 10 that is 55 checks against 2⁹ = 512 plans; for n = 40 it is 820 checks against more than half a trillion plans. The plain recursive CUT-ROD, without a table, solves the same small rods again and again and takes 2n calls; see memoization vs tabulation for that difference on a smaller example.

What the page leaves out

Rods are capped at 10 inches so the row fits on the canvas. The page leaves out the memoized top-down MEMOIZED-CUT-ROD (same table, filled on demand), a fixed cost per cut (CLRS exercise 15.1-3), a limit on how many pieces of each length can be sold, and the subproblem graph view of the recurrence.

On the mind map

This page on the Dynamic Programming mind map · 31 pages in 8 branches · open it to see the whole map and test yourself in recall mode.