Rod Cutting Problem
A rod of length n can be cut into integer pieces, where a piece of length i sells for price[i-1]. Maximise the total selling value.
Intuition
This is knapsack with unlimited copies: piece lengths can be reused as often as they fit. The trick that collapses the search is to fix only the first piece. Whatever the optimal cutting looks like, it starts with some piece of length f; the rest of the rod is then an independent, already-solved subproblem of length n − f. Trying every f and trusting dp for the remainder covers every possible cutting without ever enumerating them.
Unbounded knapsack in disguise — you may cut as many pieces of each length as you like. The recurrence tries every possible first cut and reuses the already-solved remainder, which is why one loop over lengths and one over first-cuts suffices. Compare with 0/1 knapsack: the absence of an item index is exactly what makes it unbounded.
Approach
One dimension is enough
dp[L] = best value obtainable from a rod of length L. dp[0] = 0, since a rod of nothing sells for nothing.
Fix the first cut only
dp[L] = max over f in 1..L of price[f-1] + dp[L - f]. The recursion never needs to know which pieces came before.
Sweep upward for reuse
Unlike 0/1 knapsack, dp[L - f] may already include piece f. That is correct here — pieces are unlimited, so the upward sweep is the feature, not a bug.
Solution & live demo
Common pitfalls
Recursing on both halves after a cut
best = max(best, solve(first) + solve(length - first))
best = max(best, price[first - 1] + dp[length - first])
Splitting into two subproblems double-counts arrangements and explodes the search. Fixing the first piece as a sold piece and only recursing on the remainder enumerates each partition exactly once.
Off-by-one on the price array
best = max(best, price[first] + dp[length - first])
best = max(best, price[first - 1] + dp[length - first])
price is 0-indexed while lengths are 1-indexed, so the price of a length-first piece lives at price[first - 1]. Using first directly prices every piece one size too large and overruns the array.
Restricting the first cut to lengths not yet used
for first in range(prev + 1, length + 1):
for first in range(1, length + 1):
Pieces may repeat — cutting a rod of length 4 into four length-1 pieces is legal. Any restriction on reuse turns this into the 0/1 variant and understates the profit.
Edge cases
dp[0] = 0; the loop body never executes.
f = L is one of the candidates, so the uncut rod is always considered.
Not applicable — price is indexed 1..n by definition, so every length has a price.