Rod Cutting

Rod Cutting is the classic introduction to bottom-up dynamic programming. You are given a rod and a price for every possible piece length, and you must chop it into pieces that earn the most money. The trick is that the best way to cut a long rod is built from the best ways to cut shorter rods.

The slow way first

The brute-force idea: try every possible way to chop the rod. The first cut could be at length 1, 2, 3, …, and then you recursively cut whatever is left. That branches into an exponential number of combinations — O(2ⁿ) — and re-solves the same sub-rods over and over.

The question to ask: what do I actually need to decide? Only the first cut. If I sell a leading piece of length c, the rest is a rod of length L − c, and the best revenue for that is a smaller version of the exact same problem. So if I already knew the answer for every shorter rod, the first cut would be a single max over the choices.

The idea: build short rods first

Define dp[L] = the best revenue for a rod of length L. A rod of length 0 earns nothing, so dp[0] = 0. For any longer L, try every first cut c from 1 to L:

dp[L] = max over c of ( price[c] + dp[L - c] )

Each candidate is the money from the leading piece (price[c]) plus the best we can already do with the remainder (dp[L - c], which we computed earlier). Fill dp left to right so every dp[L - c] it reads is already final.

The key insight: we never re-solve a sub-rod. Because dp is filled in increasing order of length, dp[L − c] is always a finished answer by the time dp[L] needs it.

Walk through it

Step through the animation. The top strip is price; the bottom strip is dp. The pointer L moves left to right. For each L, watch one price[c] cell and the dp[L − c] cell it reads light up — that is the winning cut — and the result drops into dp[L]. When L reaches 4, the best cut is c = 2: price[2] + dp[2] = 5 + 5 = 10.

Pseudocode

dp[0] = 0                              # an empty rod earns nothing
for L from 1 to n:                     # solve every length, short to long
    best = 0
    for c from 1 to L:                 # try every first cut
        candidate = price[c] + dp[L - c]
        best = max(best, candidate)
    dp[L] = best                       # lock in the best for length L
return dp[n]                           # the answer for the full rod

The Python solution

def rod_cutting(price, n):
    dp = [0] * (n + 1)
    for L in range(1, n + 1):
        best = 0
        for c in range(1, L + 1):
            cand = price[c - 1] + dp[L - c]
            best = max(best, cand)
        dp[L] = best
    return dp[n]

• dp[L] holds the best revenue for a rod of length L; dp[0] stays 0 (an empty rod earns nothing).
• The outer loop fills dp from short rods to long ones, so every value it reads is already final.
• The inner loop tries every first cut c. We use price[c - 1] because the list is 0-indexed but lengths start at 1.
• Lines 6 and 7 are the heart: take price[c] for the leading piece plus dp[L - c] for the remainder, and keep the best.
• dp[n] is the answer for the full rod.

Complexity

We trade O(n) space (the dp array) to collapse an exponential search into two nested loops. That move — define a sub-answer, fill it in order, and reuse it — is the core of dynamic programming.

When this pattern shows up

Practice