Rod Cutting Problem
Rod Cutting is a GeeksforGeeks practice problem (Medium), not a LeetCode one. Searches for a rod cutting problem LeetCode version usually land on 1547, Minimum Cost to Cut a Stick, which asks something different (see the comparison below).
- You are given an array
price, whereprice[i - 1]is what a piece of lengthisells for. - The rod has length
n, equal to the length ofprice. - You may cut the rod into any number of whole-number pieces, or not cut it at all, and sell every piece.
- The same piece length may be sold as many times as you like.
Return the maximum total value you can get. n goes up to 1,000, so trying every cut plan is out; an O(n²) table is expected.
- 1 <= n <= 10³
- 1 <= price[i] <= 10⁵
- Pieces must be integer lengths; unlimited cuts of each length
Intuition
The rod cutting problem looks like it needs every possible cut plan, and there are 2ⁿ⁻¹ of them. The trick is to stop thinking about all the cuts at once and look only at the first piece.
Any plan sells some first piece for its price, and what is left is a shorter rod. The best way to cut that remainder is the same question on a smaller rod, so the best total for each length is the best first piece plus the best answer already known for the rest. Because pieces of one length can be sold as often as you like, this is the unbounded knapsack pattern: rod length is the capacity, piece lengths are the items, prices are the values.
A total to split into parts, each part size with its own value, unlimited use of each size, and a best total to find. That is unbounded knapsack. Coin change (fewest coins), coin change II (count ways) and integer break use the same one-dimensional table over sizes 0..n.
Approach
Before reading on, write dp[4] for price = [1, 5, 8, 9] by hand, listing all four first-piece choices. Then decide in which order the table must be filled.
Two ways to solve it
Fill dp[1] to dp[n] in order; each cell tries every first piece and reads shorter lengths that are already done.
- Space: one array of
n + 1values. - Speed: plain loops, no calls or cache lookups.
- Safety: no recursion, so
n = 1,000is fine in any language.
This is the version to write in an interview.
Write best(L) as the recurrence itself and cache each length so it is solved only once.
- Space: a cache entry and a stack frame per length.
- Speed: the same O(n²) work, plus call overhead.
- Depth:
nlevels deep, so Python needs a raised recursion limit.
Natural to derive, but the loop is safer.
Both solve each length once in O(n²) time; the table wins because it needs no call stack, so a 1,000-long rod is safe in every language. The steps, code and live demo below follow the table, and the memoized code is further down.
Define the state
dp[L] = the maximum value obtainable from a rod of length L. The table has n + 1 cells, dp[0] to dp[n], and the answer is dp[n].
Set the base case
dp[0] = 0. A rod of length 0 sells for nothing. It is also what the "sell the whole rod uncut" choice reads: price[L - 1] + dp[0].
Write the recurrence
For each length L from 1 to n, try every first piece i from 1 to L:
dp[L] = max(price[i - 1] + dp[L - i])
The remainder L - i is always smaller than L, so filling lengths in increasing order means every value it reads is ready.
Recover the cuts, if asked
Store cut[L], the first piece that gave the maximum. Then from n, take cut[n], move to n - cut[n], and repeat until 0. The pieces listed are an optimal plan.
Rod Cutting Problem solution in Python | C++ | Java
dp[L] is the most money a rod of length L can earn, cut any way. Every cut plan starts with some first piece, sold as-is, and the rest of the rod is a smaller copy of the same problem. dp[0] = 0 anchors the chain: an empty rod earns nothing.dp[L] is the most money a rod of length L can earn, cut any way. Every cut plan starts with some first piece, sold as-is, and the rest of the rod is a smaller copy of the same problem. dp[0] = 0 anchors the chain: an empty rod earns nothing.dp[L] is the most money a rod of length L can earn, cut any way. Every cut plan starts with some first piece, sold as-is, and the rest of the rod is a smaller copy of the same problem. dp[0] = 0 anchors the chain: an empty rod earns nothing.Memoized recursion
The top-down rod cutting problem Python solution, also in C++ and Java: best(L) returns 0 for an empty rod, and otherwise the best price[i - 1] + best(L - i) over every first piece i. The cache stores each length's answer the first time, so later calls return it at once.
Common pitfalls
Recursing without memoisation
def best(L):
return max(price[i - 1] + best(L - i) for i in range(1, L + 1))for L in range(1, n + 1):
dp[L] = max(price[i - 1] + dp[L - i] for i in range(1, L + 1))The plain recursion solves best(L - i) again from every caller, which is 2ⁿ⁻¹ calls. The table solves each length exactly once.
Off-by-one between length and index
best = max(best, price[first] + dp[length - first])
best = max(best, price[first - 1] + dp[length - first])
price is 0-indexed but lengths start at 1: a piece of length 1 sells for price[0]. Reading price[first] shifts every price by one and reads past the end for first = n.
Forgetting the uncut rod
for first in range(1, length):
for first in range(1, length + 1):
first = length means no cut at all. For price = [1, 10, 12] the uncut rod (12) beats every split, and skipping it returns 11.
Complexity
L the rod cutting algorithm tries L first pieces, and 1 + 2 + … + n is about n²/2. The table is one row of n + 1 values.Rod cutting and the problems it is confused with
Three different questions share the rod picture. The table idea is shared; the rule per cell is not.
| Problem | What is chosen | Cell rule |
|---|---|---|
| Rod cutting (this page) | first piece length i, reusable | dp[L] = max(price[i-1] + dp[L-i]) |
| Rod cutting problem with cost per cut | same, but each cut costs c | max(price[L-1], max(price[i-1] + dp[L-i] - c)) |
| Unbounded knapsack | item with weight w, value v | dp[C] = max(v + dp[C-w]) |
| Minimum Cost to Cut a Stick (LeetCode 1547) | which fixed cut to make last | interval DP over cut positions, O(m³) |
Rod Cutting Problem FAQ
Why does the rod cutting problem have optimal substructure?
If an optimal plan sells a first piece of length i, the rest of that plan must be an optimal plan for length n - i. If it were not, swapping in a better plan for the rest would raise the total, contradicting optimality.
Why not cut greedily by the best price per unit length?
Because the pieces have to add up to exactly n. The best-rate length may not divide n, and the leftover can be forced into a poor piece. With price = [1, 5, 8, 9] and n = 4, length 3 has the best rate (8/3), but 3 + 1 earns 9 while 2 + 2 earns 10. The table compares every first piece, so it never gets stuck this way.