[R] Rod Cutting Problem

Start here (everyday picture). You own a long metal rod, and the shop pays different amounts for different lengths. A short piece might sell for a little, a medium piece for a lot more. The only question is: should you sell the rod whole, or saw it into shorter pieces that together earn more money? Cutting is free and you can make as many cuts as you like. That single decision — one big sale, or several smaller ones — is the whole problem.

Name the pieces (high school). Let the rod have length $n$, and let $p_i$ be the price the shop pays for a piece of length $i$. Here is the key trick: think about your first cut. If that first piece has length $i$, you pocket $p_i$ right now and you are left with a shorter rod of length $n-i$ to handle the same way. So the best revenue for length $n$, call it $r_n$, is the best first cut plus the best you can do with whatever is left: $$r_n = \max_{1 \le i \le n}\bigl(p_i + r_{n-i}\bigr), \qquad r_0 = 0.$$ Try a worked number with prices $p_1=1,\,p_2=5,\,p_3=8,\,p_4=9$ and a rod of length $4$. Selling it whole earns $9$. But two length-$2$ halves earn $5+5=10$. So $r_4 = 10$ — cutting wins.

Why dynamic programming (AP / intro-college). If you expand that recurrence by plain recursion, the same subproblem $r_{n-i}$ gets recomputed over and over — the work blows up like $2^{\,n-1}$. Dynamic programming kills the waste by computing each value once. Fill a table from the bottom up: first $r_1$, then $r_2$, all the way to $r_n$, and reuse stored answers. The outer loop runs over each length and the inner loop tries every first cut, so the cost is $1+2+\cdots+n = O(n^2)$ time with only $O(n)$ space. This is exactly the unbounded knapsack pattern: a piece of length $i$ may be reused any number of times, which is why the recurrence looks back at $r_{n-i}$ (the same length still available) rather than at a smaller item set.

Try this as you explore. Step through the trace with the >| (Next) control and watch the highlighted pseudocode line so the two nested loops become concrete. Slide n up and notice the step count grows roughly with $n^2$, not $n$ — that is the quadratic work you just derived. Then reason about a special case by hand: if every price is exactly proportional to length, $p_i = c\,i$, no cut ever helps and $r_n = p_n$ — the rod is worth selling whole. Changing one price so a medium length becomes a bargain is what makes cutting pay off, which is precisely what the $\max$ in the recurrence is hunting for.

Step 1 -- Problem Definition. Given a rod of length n and price array p[1..n] (p[i] = selling price of rod of length i), find the maximum revenue by cutting the rod into pieces. Each piece sold at its price. Unlimited cuts allowed.

Step 2 -- Optimal Substructure. First cut of length i: revenue = p[i] + max revenue from remaining rod of length n-i. Recurrence: dp[n] = max over i=1..n of (p[i] + dp[n-i]).

Step 3 -- Time O(n^2) Space O(n). Outer loop over lengths 1 to n: O(n). Inner loop over cuts 1 to length: sum 1+2+...+n = O(n^2). Space: O(n) for dp array.

Step 4 -- Comparison with Memoization. Top-down (memoization): recursive with cache. Same O(n^2) time. Bottom-up (tabulation): iterative, better cache performance, no stack overflow risk. For large n, tabulation preferred.

Step 5 -- With Cut Cost. Add a fixed cost c per cut: dp[length] = max(p[cut] + dp[length-cut] - c) for cut < length, or p[length] (no cut). This models real sawmill blade wear costs.

Step 6 -- Connection to Unbounded Knapsack. Rod cutting = unbounded knapsack where item i has weight i and value p[i], and knapsack capacity = n. The 'item' is a rod piece of length i. Same DP structure, same O(n^2) complexity.