the rod-cutting problem

You have a metal rod of integer length n and a price list telling you how much a piece of each length sells for: a piece of length 1 fetches price[1], length 2 fetches price[2], and so on. You may cut the rod into any number of integer-length pieces (or leave it whole), and you want to choose the cuts that maximize your total revenue. The twist that makes it interesting is that prices are not proportional to length — sometimes two short pieces are worth more than one long one, sometimes the reverse — so you must actually search over how to cut.

This has clean optimal substructure: the best revenue for a rod of length n is obtained by making a first cut of some length i (with 1 <= i <= n), collecting price[i] for that piece, and then cutting the remaining length n - i optimally. Since you do not know the best first piece, you try them all and keep the best. Let r(n) be the maximum revenue for length n. Then r(n) = max over i from 1 to n of ( price[i] + r(n - i) ), with base case r(0) = 0. The same r(k) values are needed by many longer rods (overlap), so dynamic programming fits: fill r[0], r[1], ..., r[n] in increasing order, each cell scanning the possible first cuts. There are n+1 states and each does O(n) work, so the whole thing is O(n^2) — a dramatic improvement over the roughly 2^(n-1) ways to cut by brute force.

Rod cutting is the canonical bridge between Fibonacci-style one-dimensional DP and richer problems: unlike Fibonacci its transition involves a maximization over many choices rather than a fixed sum, which is the first time a learner meets 'try every first move and take the best.' To recover the actual cuts, store for each length the first-cut size that achieved the maximum, then walk down: cut that size off, move to the remainder, repeat. The same template — choose a first piece, recurse on the rest — reappears in coin change and in the unbounded knapsack, so the effort spent understanding it here pays off repeatedly.