Cut Rod Problem

The Problem

You have a rod of length n inches and a price table p[1..n] where p[i] is what a piece of length i sells for. You can cut the rod into any combination of integer lengths. The goal is to maximize total revenue.

A rod of length 4 sold whole earns $9, but two pieces of length 2 earn $5 + $5 = $10. Finding the best combination by brute force takes O(2ⁿ) time — dynamic programming reduces this to O(n²).

How the Algorithm Works

• Build up from small rods. Compute the best revenue for length 1, then 2, then 3 … up to n. Each answer reuses earlier answers.
• For each length j, try every possible first cut at position i = 1 … j. The candidate revenue is p[i] + r[j−i]: sell the first piece and optimally cut the rest.
• Store the best. r[j] holds the maximum over all cuts. s[j] records which cut produced that maximum — used later to reconstruct the actual pieces.
• Reconstruct. Follow s[n] → s[n−s[n]] → … to read off the optimal cut sequence.

Reading the Visualization

• Rod bar: the red segment is the piece being sold now (length i); the blue segment is the remainder whose best revenue is already in the table.
• DP table row r[j]: fills left-to-right. The yellow cell is being computed right now; blue cells are the ones being looked up.
• DP table row s[j]: once a cell is finalized (purple), it tells you the optimal first cut for that rod length.
• Pseudocode: the highlighted line shows exactly which line of the algorithm the current step corresponds to.
• Optimal Solution (shown at the end): the colored bar divides the rod into its best pieces, each labeled with its length and sale price.