DSA Tracker

Visualize

Rod Cutting

dp[len] = max over every first cut of price(cut) + dp[len - cut]

time O(n^2)space O(n)

Look at any optimal way to cut the rod and ask: what is the FIRST piece cut off? It has some length i, sold for prices[i-1], and whatever is left is a rod of length len-i that must itself be cut optimally — that's the same problem, smaller. Trying every possible first-cut length and keeping the best gives dp[len] = max over cut of prices[cut-1] + dp[len-cut]. Because a length can be reused as many times as it helps (an unbounded supply of cuts), this is unbounded knapsack with piece lengths as weights and prices as values.

Details

Animated on: n = 8, prices = [1,5,8,9,10,17,17,20] — cut a rod of length n into pieces and sell each piece at prices[len-1] to maximize total revenue.

Problem:Rod CuttingMedium

dp[len] = max over every first cut of price(cut) + dp[len - cut]

step 1 / 10

dp over rod length — dp[len] = best revenue cutting a rod of that length

dp[0] = 0: a rod of length 0 has nothing to sell, so it earns nothing. Every longer rod's answer is built out of this.

Pseudocode
1FUNCTION rodCut(n, prices):
2  dp[0] <- 0
3  FOR len FROM 1 TO n:
4    dp[len] <- -INFINITY
5    FOR cut FROM 1 TO len:
6      dp[len] <- MAX(dp[len], prices[cut-1] + dp[len-cut])
7  RETURN dp[n]

← / → step · space play · Home restart

Every step in words

Show all 10 steps
  1. dp[0] = 0: a rod of length 0 has nothing to sell, so it earns nothing. Every longer rod's answer is built out of this.
  2. Best first cut for length 1 is 1: sell it for prices[0] = 1 and reuse dp[0] = 0 for the rest, giving dp[1] = 1.
  3. Best first cut for length 2 is 2: sell it for prices[1] = 5 and reuse dp[0] = 0 for the rest, giving dp[2] = 5.
  4. Best first cut for length 3 is 3: sell it for prices[2] = 8 and reuse dp[0] = 0 for the rest, giving dp[3] = 8.
  5. Best first cut for length 4 is 2: sell it for prices[1] = 5 and reuse dp[2] = 5 for the rest, giving dp[4] = 10.
  6. Best first cut for length 5 is 2: sell it for prices[1] = 5 and reuse dp[3] = 8 for the rest, giving dp[5] = 13.
  7. Best first cut for length 6 is 6: sell it for prices[5] = 17 and reuse dp[0] = 0 for the rest, giving dp[6] = 17.
  8. Best first cut for length 7 is 1: sell it for prices[0] = 1 and reuse dp[6] = 17 for the rest, giving dp[7] = 18.
  9. Best first cut for length 8 is 2: sell it for prices[1] = 5 and reuse dp[6] = 17 for the rest, giving dp[8] = 22.
  10. dp[8] = 22 is the best revenue for the whole rod — no combination of cuts beats it, because every one of them was already considered as some earlier dp[len]'s first cut.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Rod Cutting in the editorAll Dynamic Programming problemsBack to roadmap