Chapter 7 introduced Unbounded Knapsack and ended with a promise: every problem in the unbounded family inherits the same structure, just with a different question. Rod Cutting is the first of those problems, and it's a good one to start with because the mapping from Knapsack to Rod Cutting is clean and direct.
Once you see the mapping, the code practically writes itself.
The Problem
You have a rod of length n. For every possible piece length, there's a price you can sell it for.
price = [1, 5, 8, 9]
Length 1 → price 1
Length 2 → price 5
Length 3 → price 8
Length 4 → price 9
Cut the rod into pieces in whatever combination maximises total profit.
For a rod of length 4, some options:
Don't cut at all: length 4 → profit 9
Cut into two halves: 2 + 2 → profit 5 + 5 = 10
Cut three pieces: 1 + 1 + 2 → profit 1 + 1 + 5 = 7
Cut four pieces: 1 + 1 + 1 + 1 → profit 1 + 1 + 1 + 1 = 4
The best option here is 2 + 2 with profit 10.
One thing to notice: some versions of this problem give you both a length array and a price array. Others give only price, with the lengths implied as [1, 2, 3, ..., n]. When the length array isn't given, just construct it as range(1, n+1) where n = len(price). There's nothing more to it.
Why This Is an Unbounded Knapsack Problem
For each available piece length, you decide: use this length or don't. That's the TAKE / SKIP structure of Knapsack.
And the same piece length can be used multiple times. 2 + 2 uses the length-2 piece twice. 1 + 1 + 1 + 1 uses the length-1 piece four times. There's no restriction on repetition.
That's Unbounded Knapsack.
The variable names just change:
Unbounded Knapsack → Rod Cutting
weight → piece length
value → price
capacity → rod length
maximum value → maximum profit
The DP Table
T[i][j] = maximum profit using the first i piece lengths
for a rod of length j
Rows represent which piece lengths are available. Columns represent the rod length being considered.
Rod Length (j) →
0 1 2 3 4
Length
0 0 0 0 0 0
1 0 ? ? ? ?
2 0 ? ? ? ?
3 0 ? ? ? ?
4 0 ? ? ? ?
Base cases are the same as always: no piece lengths available means profit is 0, rod of length 0 means profit is 0. The whole table initialises to zero.
The Fit Condition: if i <= j
Before deciding TAKE or SKIP, you need to check whether the current piece actually fits in the current rod length.
Here i is the piece length and j is the rod length. So the condition is:
if i <= j:
# piece fits — TAKE or SKIP
else:
# piece too long — only SKIP
This is not anything new. It's the same fit check as in Knapsack (if wt[i-1] <= j). The difference is that in Rod Cutting, i is both the row index and the piece length. Since lengths go 1, 2, 3, ..., n and the row index goes 1, 2, 3, ..., n, the piece length at row i is simply i. So wt[i-1] from Knapsack becomes just i.
The Transition
When the piece fits:
T[i][j] = max(
price[i-1] + T[i][j-i], # TAKE: same row (unbounded)
T[i-1][j] # SKIP: previous row
)
The TAKE branch subtracts i from j (the piece length from the rod length) and stays at row i. Staying at row i means the same piece length is still available, so it can be picked again. That's the unbounded behaviour from Chapter 7.
When the piece doesn't fit:
T[i][j] = T[i-1][j] # only SKIP is possible
A Small Dry Run
For price = [1, 5, 8, 9], consider i = 2, j = 4:
2 <= 4 → piece fits
T[2][4] = max(
price[1] + T[2][4-2],
T[1][4]
)
= max(
5 + T[2][2],
T[1][4]
)
T[2][2] is at the same row i = 2. That cell can itself pick another length-2 piece since 2 <= 2. So 2 + 2 is a valid selection. The unbounded behaviour is visible here in a concrete cell computation.
The Complete Code
class Solution:
def cutRod(self, price):
n = len(price)
# T[i][j] = max profit using first i piece lengths
# for a rod of length j.
# Initialised to 0 — handles both base cases.
T = [[0] * (n + 1) for _ in range(n + 1)]
# i is both the row index and the piece length
# (lengths are 1-indexed: 1, 2, ..., n)
for i in range(1, n + 1):
for j in range(1, n + 1):
if i <= j:
# Piece fits — TAKE or SKIP
T[i][j] = max(
price[i - 1] + T[i][j - i], # TAKE: stay at row i
T[i - 1][j] # SKIP: move to row i-1
)
else:
# Piece too long — only SKIP
T[i][j] = T[i - 1][j]
# Answer: all piece lengths considered, full rod length
return T[n][n]
Compare this with the Unbounded Knapsack code from Chapter 7. The only structural difference is if i <= j instead of if wt[i-1] <= j, and T[i][j-i] instead of T[i][j-wt[i-1]]. Both simplifications happen because piece length at row i is just i.
The Pattern Connection
Quick Revision
The mapping:
Knapsack weight → piece length (i)
Knapsack value → price[i-1]
Knapsack capacity → rod length (j)
The fit condition:
if i <= j: # piece length fits in rod length
The transition:
T[i][j] = max(
price[i-1] + T[i][j-i], # TAKE: same row (unbounded)
T[i-1][j] # SKIP: previous row
)
When length array isn't given:
lengths are implicitly [1, 2, 3, ..., n]
where n = len(price)
What You Now Understand
Rod Cutting is Unbounded Knapsack with renamed variables. The fit condition i <= j is just checking whether the piece is short enough to fit in the remaining rod. The TAKE branch stays on the same row because the same piece length can be used again.
Chapter 9 continues the Unbounded family with Coin Change I: instead of maximising profit, you're minimising the number of coins to reach a target amount. The choice structure stays the same. The operation changes from max to min, and the initialisation needs one careful adjustment because of it.
Top comments (0)