Rod Cutting Problem
What you'll learn: How to maximize profit by cutting a rod into pieces where each length has a different selling price.
The Core Idea
Imagine you own a rod of length n and a price list that tells you how much you can sell rods of different lengths for. Your goal is to decide how to cut the rod (or not cut it at all) to make the most money.
For example, if you have a rod of length 4 and these prices:
- Length 1: $2
- Length 2: $5
- Length 3: $7
- Length 4: $8
You might think selling the whole rod for 5 + 10!
Why It's a DP Problem
This problem has overlapping subproblems and optimal substructure:
- If you make a cut at position
i, you split the problem into "what's the best way to sell a rod of lengthi" and "what's the best way to sell the remaining lengthn-i" - You'll repeatedly solve the same subproblems (like "best profit for length 2") when considering different cut combinations
The DP Approach
Define dp[i] = maximum profit from a rod of length i
For each length, try all possible first cuts and pick the best:
dp[i] = max(price[i], max(dp[j] + dp[i-j]) for all j < i)
You either sell the whole rod at price[i] or make a cut somewhere and combine optimal solutions for the pieces.
Key Takeaway: The Rod Cutting Problem uses DP to try all cutting possibilities efficiently, storing optimal solutions for each length and building up to the full rod, transforming an exponential problem into O(n²) time.