Course contentsShow
← Computer Science
Lesson 934 of 2,87222. Dynamic ProgrammingFree lesson

Rod Cutting Problem

Maximize profit by cutting a rod into pieces of various lengths with different prices per length.

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 8isbest,butcuttingitintotwopiecesoflength2eachgivesyou8 is best, but cutting it into two pieces of length 2 each gives you 5 + 5=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 length i" and "what's the best way to sell the remaining length n-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.