Rod Cutting

Rod cutting works by exploiting the fact that the best way to cut a rod of length n is to pick some first-piece length i (1≤i≤n), sell it for price[i], and then optimally cut the remaining rod of length n-i — a smaller instance of the exact same problem — so the optimal value combines a choice with a recursively optimal subproblem, which is the signature of dynamic programming.

Recognize the pattern

• You're told to divide a resource (length, weight, budget) into pieces, each piece has an independent value, and you want to maximize total value.
• The choice at each step is "how big is the first/next piece" and the rest of the resource must still be fully accounted for.
• Pieces can repeat (unbounded) — unlike 0/1 knapsack, you may cut two pieces of length 2 from a rod of length 5.
• It reduces to unbounded knapsack: item weight = piece length, item value = piece price, capacity = rod length.

Brute force to optimal

Brute force: for a rod of length n, try every first cut length i from 1..n and recurse on n-i, taking the max. This is the recurrence cut(n) = max over i in [1,n] of price[i] + cut(n-i), with cut(0) = 0. Because cut(n-i) is recomputed from scratch for overlapping subproblem sizes, this branches like a full recursion tree: cost is exponential, roughly O(2^n).

Optimal: memoize (top-down) or tabulate (bottom-up) on the single parameter n, since the subproblem is fully described by remaining length. There are only n+1 distinct subproblems (lengths 0..n), each solved once in O(n) work (trying every cut), giving O(n^2) total.

Complexity from first principles

Time: there are n+1 distinct states (dp[0..n]). Computing dp[len] requires trying every cut i from 1 to len, i.e. up to len iterations. Total work = ∑_len=1ⁿ len = n(n+1)/2 = O(n²). Each iteration does O(1) arithmetic, so no hidden log factors.

Space: dp array of size n+1 → O(n). (If you also track the chosen first-cut per length to reconstruct the actual pieces, that's another O(n) array — still O(n) total.) No extra space needed beyond that; the bottom-up loop uses O(1) auxiliary space per state.

Worked example

price = [_, 2, 6, 7, 10, 13] (1-indexed by length), n = 5. This is a small example adapted for illustration, not CLRS's own price table (CLRS uses n=10 with price=[1,5,8,9,10,17,17,20,24,30]) — the recurrence and mechanism are identical either way. Bottom-up: dp[len] = max over i=1..len of price[i] + dp[len-i].

dp[5] = 14, matching the brute-force check (two pieces of length 2 + one of length 1: 6+6+2=14).

Java implementation (bottom-up, with reconstruction)

public class RodCutting {
    // price[i] = price of a piece of length i (1-indexed); price[0] unused.
    public static int maxProfit(int[] price, int n) {
        int[] dp = new int[n + 1];
        int[] cut = new int[n + 1]; // first-cut length chosen at each len
        for (int len = 1; len <= n; len++) {
            int best = Integer.MIN_VALUE, bestI = -1;
            for (int i = 1; i <= len; i++) {
                int candidate = price[i] + dp[len - i];
                if (candidate > best) {
                    best = candidate;
                    bestI = i;
                }
            }
            dp[len] = best;
            cut[len] = bestI;
        }
        // Optional: reconstruct pieces
        int len = n;
        StringBuilder pieces = new StringBuilder();
        while (len > 0) {
            pieces.append(cut[len]).append(" ");
            len -= cut[len];
        }
        System.out.println("Pieces: " + pieces.toString().trim());
        return dp[n];
    }
}

Go implementation (bottom-up, with reconstruction)

package main

import "fmt"

// price[i] = price of a piece of length i (1-indexed); price[0] unused.
func maxProfit(price []int, n int) int {
	dp := make([]int, n+1)
	cut := make([]int, n+1) // first-cut length chosen at each len
	for length := 1; length <= n; length++ {
		best, bestI := -1<<31, -1
		for i := 1; i <= length; i++ {
			candidate := price[i] + dp[length-i]
			if candidate > best {
				best = candidate
				bestI = i
			}
		}
		dp[length] = best
		cut[length] = bestI
	}
	// Optional: reconstruct pieces
	pieces := []int{}
	for length := n; length > 0; length -= cut[length] {
		pieces = append(pieces, cut[length])
	}
	fmt.Println("Pieces:", pieces)
	return dp[n]
}

Pitfalls

• Off-by-one on indexing: price is naturally 1-indexed (piece length 1..n); using price[0] as length-1 price shifts everything.
• Confusing with 0/1 knapsack: rod cutting allows reusing the same length multiple times (unbounded), so the inner loop must allow i to be picked again for smaller remaining lengths — do not decrement an "item pool".
• Forgetting price[i] may not exist for all i: if prices are only given for a subset of lengths, uncomputed price[i] must be excluded (e.g. treat as -infinity), not silently 0.
• Not handling non-integer / arbitrary cut costs — if there's a fixed cost per cut, the recurrence must subtract it, changing the recurrence's optimal structure.

When to use / when not — trade-offs

Use bottom-up O(n^2) DP whenever the rod length n is the state and cuts are unbounded/reusable — it's simple, iterative, and avoids recursion overhead. Compare against:

• Greedy (always cut the piece with best price/length ratio): O(n log n) for sorting, but fails to find the optimum in general — greedy locally maximizes rate but ignores how the *remainder* combines, so it does not have the optimal-substructure guarantee DP provides. Only correct if prices are provably proportional/convex in a specific way.
• Memoized top-down recursion: same O(n^2) time and O(n) space (plus call-stack depth O(n)), often more intuitive to write but pays recursion overhead; prefer bottom-up for tight performance or very large n (avoids stack-depth limits).
• Brute-force recursion (no memo): only viable for tiny n (say n≤15) or when demonstrating the exponential blow-up.

Takeaways

• Rod cutting = unbounded knapsack in disguise: state is remaining length, decision is next piece length.
• Optimal substructure + overlapping subproblems on a single integer parameter n gives O(n^2) time, O(n) space via bottom-up DP.
• Track the chosen cut per length to reconstruct the actual pieces, not just the value.
• Greedy by price/length ratio is a tempting but incorrect shortcut — always verify against DP on a small counterexample.

Recall: Why is rod cutting solvable with just an O(n) dp array instead of a 2D table like 0/1 knapsack?

Adapted from CLRS (Cormen, Leiserson, Rivest, Stein), "Introduction to Algorithms", Ch. 15 (Dynamic Programming) — Rod Cutting section; standard unbounded-knapsack DP formulation. Worked-example price values are adapted for a compact walkthrough, not CLRS's own table.