Rod Cutting Problem: Maximum Revenue DP
You have a steel rod of length n inches. Your supplier buys rod pieces at different prices depending on their length. The question: how should you cut the rod to maximize revenue?
Key Insights
- The rod cutting problem demonstrates why greedy optimization fails for problems with overlapping subproblems—the highest price-per-unit cut often leads to suboptimal total revenue
- Bottom-up dynamic programming solves rod cutting in O(n²) time with O(n) space, transforming an exponential recursive problem into a polynomial one
- Tracking cut decisions alongside maximum values lets you reconstruct the actual solution, which matters more than the optimal value in production systems
Introduction to the Rod Cutting Problem
You have a steel rod of length n inches. Your supplier buys rod pieces at different prices depending on their length. The question: how should you cut the rod to maximize revenue?
This isn’t a toy problem. Manufacturing facilities face this daily when cutting raw materials—steel bars, lumber, fabric rolls, cable spools. Resource allocation systems solve variants when partitioning compute resources or time slots. Even content platforms use similar logic when deciding how to segment video content for different distribution channels.
The problem setup is straightforward. Given a price table where price[i] represents the selling price for a rod of length i, find the maximum revenue obtainable from a rod of length n. You can sell the rod whole, cut it into pieces, or any combination.
For example, with prices [0, 1, 5, 8, 9, 10, 17, 17, 20] (index 0 unused, length 1 costs $1, length 2 costs $5, etc.), what’s the maximum revenue for a rod of length 4?
Why Greedy Fails
Your first instinct might be greedy: calculate price-per-inch for each length and always cut the most valuable piece. This fails spectacularly.
Using our price table, the price-per-inch ratios are:
- Length 1: $1.00/inch
- Length 2: $2.50/inch
- Length 3: $2.67/inch
- Length 4: $2.25/inch
A greedy algorithm would prioritize length-3 cuts. For a rod of length 4, it would cut one piece of length 3 ($8) and one piece of length 1 ($1), totaling $9.
But cutting into two pieces of length 2 yields $5 + $5 = $10. Greedy left money on the table.
def greedy_rod_cutting(prices, n):
"""
Greedy approach: always take the best price-per-unit cut.
This produces SUBOPTIMAL results!
"""
if n == 0:
return 0, []
# Calculate price per unit for each length
price_per_unit = [(prices[i] / i, i) for i in range(1, len(prices))]
price_per_unit.sort(reverse=True) # Best ratio first
total_revenue = 0
cuts = []
remaining = n
for ratio, length in price_per_unit:
while remaining >= length:
remaining -= length
total_revenue += prices[length]
cuts.append(length)
return total_revenue, cuts
# Example showing greedy failure
prices = [0, 1, 5, 8, 9, 10, 17, 17, 20]
revenue, cuts = greedy_rod_cutting(prices, 4)
print(f"Greedy result: ${revenue} with cuts {cuts}") # $9 with [3, 1]
print(f"Optimal result: $10 with cuts [2, 2]") # Greedy missed this
The problem has overlapping subproblems. To find the optimal cut for length 4, you need optimal solutions for lengths 1, 2, and 3. Those subproblems share even smaller subproblems. This structure screams dynamic programming.
Recursive Solution & Optimal Substructure
The optimal substructure is clean: the maximum revenue for a rod of length n equals the maximum over all possible first cuts. If you make a cut of length i, you get price[i] plus the optimal revenue from the remaining n-i inches.
The recurrence relation:
maxRevenue(n) = max(price[i] + maxRevenue(n - i)) for i in 1..n
Base case: maxRevenue(0) = 0 (no rod, no revenue).
def rod_cutting_recursive(prices, n):
"""
Naive recursive solution.
Time complexity: O(2^n) - exponential!
"""
if n == 0:
return 0
max_revenue = float('-inf')
for i in range(1, n + 1):
if i < len(prices):
revenue = prices[i] + rod_cutting_recursive(prices, n - i)
max_revenue = max(max_revenue, revenue)
return max_revenue
# This works but is painfully slow for large n
prices = [0, 1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting_recursive(prices, 4)) # 10
The call tree explodes exponentially. For n=4, the recursion computes rod_cutting(2) multiple times—once when considering a cut of 2, and again when considering cuts of 1+1. The time complexity is O(2^n) because each length has two choices: cut here or don’t.
rod_cutting(4)
├── rod_cutting(3) [cut 1]
│ ├── rod_cutting(2) [cut 1]
│ │ ├── rod_cutting(1)
│ │ └── rod_cutting(0)
│ ├── rod_cutting(1) [cut 2]
│ └── rod_cutting(0) [cut 3]
├── rod_cutting(2) [cut 2] <- DUPLICATE
│ ├── rod_cutting(1)
│ └── rod_cutting(0)
├── rod_cutting(1) [cut 3]
└── rod_cutting(0) [cut 4]
Top-Down DP with Memoization
The fix is simple: cache results. Before computing maxRevenue(k), check if you’ve already solved it. If yes, return the cached value. If no, compute it, cache it, then return.
def rod_cutting_memo(prices, n, memo=None):
"""
Top-down DP with memoization.
Time complexity: O(n²)
Space complexity: O(n) for memo + O(n) for call stack
"""
if memo is None:
memo = {}
if n == 0:
return 0
if n in memo:
return memo[n]
max_revenue = float('-inf')
for i in range(1, n + 1):
if i < len(prices):
revenue = prices[i] + rod_cutting_memo(prices, n - i, memo)
max_revenue = max(max_revenue, revenue)
memo[n] = max_revenue
return max_revenue
prices = [0, 1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting_memo(prices, 8)) # 22
The memoization table fills incrementally. For n=4:
memo[0] = 0(base case)memo[1] = 1(only one cut possible)memo[2] = 5(length 2 beats two length-1 cuts)memo[3] = 8(length 3 beats alternatives)memo[4] = 10(two length-2 cuts)
Each subproblem is solved exactly once. With n subproblems and O(n) work per subproblem (trying all cut positions), total time is O(n²).
Bottom-Up DP (Tabulation)
Bottom-up avoids recursion overhead entirely. Build the solution table from smallest subproblems upward.
def rod_cutting_tabulation(prices, n):
"""
Bottom-up DP with tabulation.
Time complexity: O(n²)
Space complexity: O(n)
"""
# dp[i] = maximum revenue for rod of length i
dp = [0] * (n + 1)
for length in range(1, n + 1):
max_revenue = float('-inf')
# Try all possible first cuts
for cut in range(1, length + 1):
if cut < len(prices):
revenue = prices[cut] + dp[length - cut]
max_revenue = max(max_revenue, revenue)
dp[length] = max_revenue
return dp[n]
prices = [0, 1, 5, 8, 9, 10, 17, 17, 20]
print(rod_cutting_tabulation(prices, 8)) # 22
The table construction is deterministic. When computing dp[length], all smaller subproblems dp[0] through dp[length-1] are already solved. No recursion, no stack overflow risk, and better cache locality.
For our example with n=8, the final table:
dp = [0, 1, 5, 8, 10, 13, 17, 18, 22]
Maximum revenue for length 8 is $22.
Reconstructing the Optimal Cuts
Knowing the maximum revenue is useful. Knowing which cuts achieve it is essential for actually running a manufacturing line.
Track the first cut made at each length. Then backtrack from the final solution.
def rod_cutting_with_solution(prices, n):
"""
Bottom-up DP that tracks and reconstructs optimal cuts.
Returns (max_revenue, list_of_cuts)
"""
dp = [0] * (n + 1)
first_cut = [0] * (n + 1) # first_cut[i] = optimal first cut for length i
for length in range(1, n + 1):
max_revenue = float('-inf')
best_cut = 0
for cut in range(1, length + 1):
if cut < len(prices):
revenue = prices[cut] + dp[length - cut]
if revenue > max_revenue:
max_revenue = revenue
best_cut = cut
dp[length] = max_revenue
first_cut[length] = best_cut
# Reconstruct the solution
cuts = []
remaining = n
while remaining > 0:
cuts.append(first_cut[remaining])
remaining -= first_cut[remaining]
return dp[n], cuts
prices = [0, 1, 5, 8, 9, 10, 17, 17, 20]
revenue, cuts = rod_cutting_with_solution(prices, 8)
print(f"Maximum revenue: ${revenue}") # $22
print(f"Optimal cuts: {cuts}") # [2, 6] or [6, 2]
The first_cut array adds O(n) space but provides the actual solution. For length 8 with our prices, the optimal cuts are [2, 6]—a piece of length 2 ($5) and a piece of length 6 ($17), totaling $22.
Variations & Extensions
The basic rod cutting problem has several practical extensions.
Limited quantities: What if you can only sell at most k pieces of each length? This transforms the problem into a bounded knapsack variant. Track quantities used and add constraints.
def rod_cutting_limited(prices, n, max_pieces):
"""
Rod cutting with limited pieces per length.
max_pieces[i] = maximum pieces of length i allowed.
"""
dp = [0] * (n + 1)
for length in range(1, n + 1):
for cut in range(1, length + 1):
if cut < len(prices):
# Count how many pieces of this cut we'd use
# This is a simplification - full solution needs 2D DP
revenue = prices[cut] + dp[length - cut]
dp[length] = max(dp[length], revenue)
return dp[n]
Cutting costs: Each cut might have an associated cost (saw blade wear, labor time). Subtract cutting cost from revenue when making each cut.
2D rod cutting: Cutting rectangular sheets (glass, metal, fabric) extends to two dimensions. The state space becomes O(n²m²) for an n×m sheet, with cuts along either axis.
Unbounded knapsack connection: Rod cutting is actually unbounded knapsack in disguise. The rod length is your knapsack capacity. Each possible cut length is an item with weight equal to its length and value equal to its price. You can use each “item” unlimited times.
def unbounded_knapsack(weights, values, capacity):
"""
Same algorithm, different framing.
For rod cutting: weights = [1,2,3,...], values = prices
"""
dp = [0] * (capacity + 1)
for cap in range(1, capacity + 1):
for i in range(len(weights)):
if weights[i] <= cap:
dp[cap] = max(dp[cap], values[i] + dp[cap - weights[i]])
return dp[capacity]
This connection means techniques from knapsack literature—branch and bound, approximation algorithms, parallel implementations—apply directly to rod cutting variants.
The rod cutting problem is a gateway to understanding how dynamic programming transforms exponential search spaces into polynomial-time solutions. Master this pattern, and you’ll recognize it everywhere: resource allocation, sequence alignment, parsing, and countless optimization problems hiding in production codebases.