1. One-Liner
Rod cutting maximizes total price for a rod of length n using price table p[i] for length-i pieces—unbounded DP over lengths like unbounded knapsack on one dimension.
2. The Problem It Solves
You can cut a rod into integer lengths; each length has a market price. Find cuts (or no cut) maximizing sum of piece prices—classic unbounded composition problem.
3. The Core Idea
For each length L, try every first cut size i: dp[L] = max_i (p[i] + dp[L-i]) with dp[0]=0—build up from shorter rods.
4. How It Works (Step-by-Step)
| Step | What Happens |
|---|---|
| 1 | dp[0]=0 |
| 2 | For L from 1 to n |
| 3 | For each cut i≤L, relax dp[L] |
| 4 | Return dp[n] |
5. Dry Run Example
Prices p[1]=1, p[2]=5, p[3]=8, n=4: best is two pieces of length 2 → 10.
6. Key Properties
| Property | Value |
|---|---|
| Structure | 1D unbounded |
| Time | O(n²) naive |
7. Where It Is Used
| Domain | Use |
|---|---|
| OR | Cutting stock (simplified) |
| Interviews | Unbounded DP pattern |
8. Interview Tips
Relate to coin change (max); discuss constraints if cuts are limited.
9. Comparison with Other Algorithms
| Problem | Variant |
|---|---|
| Rod cutting | Maximize price |
| Min squares | Different cost |
10. Complexity
| Metric | Value |
|---|---|
| Time | O(n²) with naive transitions |
| Space | O(n) |
Implementation Example (PYTHON)
def rod_cutting_max(price: list[int], n: int) -> int:
dp = [0] * (n + 1)
for L in range(1, n + 1):
best = 0
for i in range(1, L + 1):
if i <= len(price):
best = max(best, price[i - 1] + dp[L - i])
dp[L] = best
return dp[n]