Rod Cutting

You have one rod of integer length n. You are given a price table p: the value of selling a single piece of length i is p[i] (for i = 1, 2, …, n). Length 0 has no piece, so p[0] = 0 is only a notational convenience.

You may cut the rod into any number of pieces (including one piece of full length n, meaning no cuts). Pieces cannot overlap and must add up to the full length. Your goal is to maximize the sum of the prices of all pieces.

Example idea: If n = 4 and your table says a piece of length 2 is very valuable, an optimal plan might be two pieces of length 2, or one piece of length 1 plus one of length 3 — whichever sum p[·] is largest. The DP recurrence below tries every sensible “first cut” and recurses on what is left.

Meaning of the state. Let dp(k) be the best (maximum) total price you can get from a rod of length k (using the same price table, for any k between 0 and n).

Idea in words. Look at the left end of a rod of length k. The first piece you sell has some length i. That length i must be at least 1 and at most k (you cannot take a piece longer than the rod). You earn p[i] for that first piece. Whatever is left is a shorter rod of length k − i; you will cut that remainder optimally, which by definition is worth dp(k − i).

So for a fixed choice of i, one full plan has total value:

You do not know i in advance, so you try all possibilities from 1 to k and keep the largest total:

Written as a loop (same math, often easier to read than compact symbols):

Note p[k] + dp(k − k) is p[k] + dp(0) — that is the option “sell the whole rod as one piece and nothing remains.”

Why this is correct. Any optimal solution cuts a rod of length k into some first piece of length i and some optimal cutting of the rest. If the rest were not optimal, you could replace it with a better cutting of length k − i and strictly increase the total — so the remainder must be solved optimally (dp(k − i)). Trying every i covers all first-piece choices, so the maximum is exactly dp(k).

Without memory, the same dp(k) would be recomputed many times. Keep an array memo[0] … memo[n].

• Use a value like −1 to mean “not computed yet.” (After you compute dp(k), the answer is always ≥ 0, so −1 is safe as “empty.”)
• When asked for dp(k), if memo[k] is already filled, return it.
• Otherwise compute dp(k) with the recurrence: a for loop over i = 1 … k, each time evaluating p[i] + dp(k − i) (recursive calls on smaller lengths k − i). Store the best value in memo[k] and return.

How many subproblems? Only lengths 0 … n, so n + 1 states. For each k, you try up to k values of i, so overall time is on the order of 1 + 2 + … + n, i.e. O(n²). Space is O(n) for memo plus the recursion stack.

The recurrence for dp(k) needs a place to stop. When no rod is left, there is nothing to sell:

How it connects to the formula. In the loop over i, the case i = k uses p[k] + dp(k − k) = p[k] + dp(0) = p[k]. So “no cut” (one piece of the full length) is already included; you do not need a separate rule for it.

Every recursive chain eventually reaches dp(0) because each step replaces length k by a strictly smaller length k − i with i ≥ 1.

A manufacturer has a single steel rod of length 4 (measured in integer units). The rod may be cut into any number of shorter rods at integer positions; cutting itself has no cost. Each resulting piece is sold separately, and the revenue for a piece depends only on its length, according to this price table:

The pieces you sell must partition the original rod: their lengths are positive integers that sum to 4, and your total revenue is the sum of the prices of those pieces.

(a) What is the maximum total revenue you can obtain from this one rod?

(b) Describe one best way to cut and sell the rod. In plain words: how many pieces do you end up with, and how long is each piece? (It does not matter which end you cut from first — only the list of piece lengths matters.)

Solution. Work in two layers: first list every cutting plan (so the answer is visible without DP), then replay the same logic using dp(k) so it matches the recurrence you learned above.

Part A — Enumerate all plans (length 4 only)

Ignore the order of pieces along the rod; only the multiset of lengths matters. Every partition of 4 into positive integers gives one case:

1. One piece of length 4 (no cuts) → revenue p[4] = 9.
2. Lengths 3 and 1 → p[3] + p[1] = 8 + 1 = 9.
3. Two pieces of length 2 → p[2] + p[2] = 5 + 5 = 10.
4. Lengths 2, 1, and 1 → p[2] + p[1] + p[1] = 5 + 1 + 1 = 7.
5. Four pieces of length 1 → 4 × p[1] = 4.

Compare the totals: 9, 9, 10, 7, 4. The largest is 10.

• (a) Maximum total revenue = 10.
• (b) In simple terms: cut once in the middle so the rod becomes two separate pieces, each 2 units long. You sell the first piece for 5 and the second piece for 5, so you earn 5 + 5 = 10 in total. (As a list of lengths, that plan is 2 + 2.)

Part B — Same numbers via subproblems (builds up dp(1) … dp(4))

Let dp(k) = maximum revenue from a rod of length k (same price table). Empty rod: dp(0) = 0.

Step 1 — Length 1. You can only sell one piece of length 1 → dp(1) = p[1] = 1.

Step 2 — Length 2. Take a first piece of length i (where i is 1 or 2); you earn p[i], and the rest has length 2 − i, worth dp(2 − i):

• i = 1: p[1] + dp(1) = 1 + 1 = 2 (one unit off, then best on the remaining unit).
• i = 2: p[2] + dp(0) = 5 + 0 = 5 (sell the whole length-2 rod as one piece).

Best of {2, 5} → dp(2) = 5.

Step 3 — Length 3. First piece i ∈ {1, 2, 3}:

• i = 1: p[1] + dp(2) = 1 + 5 = 6.
• i = 2: p[2] + dp(1) = 5 + 1 = 6.
• i = 3: p[3] + dp(0) = 8 + 0 = 8.

Best → dp(3) = 8.

Step 4 — Length 4. First piece i ∈ {1, 2, 3, 4}:

• i = 1: p[1] + dp(3) = 1 + 8 = 9.
• i = 2: p[2] + dp(2) = 5 + 5 = 10 ← best.
• i = 3: p[3] + dp(1) = 8 + 1 = 9.
• i = 4: p[4] + dp(0) = 9 + 0 = 9 (this is exactly “sell uncut”).

So dp(4) = 10, coming from i = 2: you take a first piece of length 2, then best revenue on the leftover length 2 is dp(2) = 5 (one piece of length 2). That is the same idea as two length-2 pieces in plain English. The option i = 4 means no cut — one piece only — and pays 9, which is not the maximum here.

Recursive DP with memoization:

Time: O(n²) — state k does O(k) work. Space: O(n) for memo, plus O(n) recursion depth in the worst case.