Rod Cutting DP, in depth: the first-piece recurrence, a full worked table, reconstruction, cut costs, piece limits and pseudo-polynomial time

The problem and why brute force fails

Formally: given n and prices p[1..m], choose positive integers that sum to n, each at most m, to maximise the sum of their prices. A length-n rod has n - 1 possible cut positions, each cut or not, so there are 2^n-1 cut patterns. For n = 40 that is about 550 billion. Enumerating them is hopeless beyond tiny inputs, but every pattern decomposes the same way, and that is the opening for dynamic programming.

We use the price table from the classic textbook treatment, for lengths 1 to 10:

The recurrence: fix the first piece

Look at any optimal solution for length j and consider its leftmost piece. Say it has length i. The rest is a rod of length j - i, and the pieces cut from it must themselves be an optimal solution for that length. If they were not, swapping in a better solution for the remainder would improve the whole, contradicting optimality. That is optimal substructure. Since we do not know i in advance, we try every value:

r[0] = 0
r[j] = max over i in 1..min(j, m) of ( p[i] + r[j - i] )

Here r[j] is the best revenue for length j, and the case i = j means selling the rod uncut. Fixing the first piece rather than the cut position is what keeps this a one-dimensional recurrence. Choosing a split point and solving both halves recursively also works, but it is slower and counts the same pattern several times.

The recurrence is an unbounded knapsack in which each item's weight is its length: lengths are item weights, prices are values, and each length can be used any number of times. The knapsack article treats that family in general. Here we stay with what is specific to cutting.

Bottom-up implementation with reconstruction

Bottom-up evaluation fills r from 1 to n; each entry reads only smaller entries, so a single forward pass is a legal order. Alongside each r[j] store the first cut that achieved it; that array is all you need to reconstruct the answer. The version below also supports a fixed cost per cut, which we use later.

def cut_rod(prices, n, cut_cost=0):
    """prices[i] = price of a piece of length i (prices[0] unused).
    Returns (best revenue, list of piece lengths)."""
    m = len(prices) - 1
    best = [0] * (n + 1)
    first = [0] * (n + 1)
    for j in range(1, n + 1):
        best[j] = float("-inf")
        for i in range(1, min(j, m) + 1):
            value = prices[i] + best[j - i] - (cut_cost if i < j else 0)
            if value > best[j]:
                best[j], first[j] = value, i
    pieces, j = [], n
    while j > 0:
        pieces.append(first[j])
        j -= first[j]
    return best[n], pieces

prices = [0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30]
print(cut_rod(prices, 8))      # (22, [2, 6])
print(cut_rod(prices, 7, 2))   # (17, [7])

A memoised top-down version computes the same table in the same time and only touches lengths that are actually reachable, which matters when prices exist for only a few lengths. In Python it hits the default recursion limit of 1,000 frames near n = 1,000, so prefer the loop for large rods or raise the limit deliberately.

Worked example: filling the table

Walk the first few entries by hand. r[1] = 1. For length 2 the options are 1 + r[1] = 2 or 5 uncut, so 5. For length 3, 1 + 5 = 6, 5 + 1 = 6, or 8 uncut: 8. For length 4, 1 + 8 = 9, 5 + 5 = 10, 8 + 1 = 9, or 9 uncut: the best is 10, two pieces of length 2. The full results are:

Ties exist: length 7 also reaches 18 as 2 + 2 + 3. The code keeps the first maximum it finds, because it uses a strict comparison. If you need a canonical answer, such as fewest pieces, make that a secondary key explicitly rather than relying on loop order.

Why greedy by price per unit fails

The tempting shortcut is to sort lengths by price per unit and cut the best-density piece as often as it fits. With the table above that fails at length 4: the best density that fits is length 3 at 2.67, which leaves a piece of length 1, for 8 + 1 = 9. The optimum is 5 + 5 = 10, using length 2 at only 2.50 per unit. Greedy commits to a locally attractive piece without accounting for the leftover it forces, and the leftover is where it loses. Density does matter for very long rods, where the best-density length tends to dominate, and the coin change article shows how to exploit that kind of structure for huge targets. For exact answers at ordinary sizes, use the DP.

Variants that change the state

Real cutting problems rarely match the textbook. Each variant below changes the state or the transition, and the brute-force checker in the next section catches the cases where you get that wrong.

Cost per cut. If every cut costs c (saw time, blade wear), subtract c whenever the first piece is not the whole rod, as cut_cost if i < j else 0 does above. With c = 2 the answers change: length 4 now sells whole for 9 (two halves give 10 - 2 = 8), length 5 gives 11 instead of 13, and length 7 sells whole for 17 rather than 18 - 2 = 16. Cut costs push solutions towards fewer pieces.

Material lost per cut. A saw blade removes material, called kerf. Each cut then consumes k units in addition to the pieces, so the state must track material remaining, and the last piece needs no kerf after it. The transition becomes p[i] + r[j - i - k] for non-final pieces. Trailing scrap must also be allowed, because a perfect fit is no longer guaranteed.

At most K pieces. A packing line can only handle a few pieces per rod. Add the piece count to the state: r[k][j] is the best revenue using at most k pieces. The cost grows by a factor of K. With the prices above, length 7 earns 17 with one piece and 18 with two or more.

Missing lengths. If only some lengths sell, some j may be impossible to fill exactly. Initialise unreachable states to minus infinity rather than 0, or allow a zero-price scrap piece of length 1 if waste is acceptable. Initialising to 0 silently treats leftover material as free and sellable.

Many rods, given demand. Cutting several stock rods to meet orders for given quantities is the cutting stock problem, an integer program. The standard approach, Gilmore-Gomory column generation, repeatedly solves a knapsack-style pricing problem to find the next cutting pattern. Single-rod revenue maximisation is that subproblem.

Testing against brute force

DP bugs hide in boundaries: an off-by-one in the inner loop, a wrong initial value, a cut cost charged on the uncut case. A brute-force oracle over all 2^n-1 patterns is cheap for n up to about 12 and catches all of them. Random prices, random price-list lengths shorter than n and random cut costs exercise every branch.

import random

def brute(prices, n, cut_cost=0):
    best = float("-inf")
    for mask in range(1 << (n - 1)):
        pieces, run = [], 1
        for b in range(n - 1):
            if mask >> b & 1:
                pieces.append(run); run = 1
            else:
                run += 1
        pieces.append(run)
        if max(pieces) < len(prices):
            best = max(best, sum(prices[x] for x in pieces) - cut_cost * (len(pieces) - 1))
    return best

for _ in range(500):
    n = random.randint(1, 12)
    m = random.randint(1, n)
    prices = [0] + [random.randint(0, 30) for _ in range(m)]
    c = random.choice([0, 0, 1, 3])
    value, pieces = cut_rod(prices, n, c)
    assert value == brute(prices, n, c), (prices, n, c)
    assert sum(pieces) == n
    assert value == sum(prices[x] for x in pieces) - c * (len(pieces) - 1)

The last two assertions matter as much as the first. A DP can return the right value while reconstruction is broken, for example when first is updated with >= in one place and > in another. Checking that the reconstructed pieces reproduce the reported revenue catches that.

Complexity: polynomial in the value, not the input

The double loop runs n × min(n, m) iterations, so O(n²) when every length has a price and O(nm) when only lengths up to m do. Space is O(n). That looks polynomial, but n is a number in the input, not a count of input items. Writing n = 10¹² takes thirteen digits, yet the table would need a trillion entries. Like knapsack, rod cutting is pseudo-polynomial: fast when lengths are small integers, impractical when they are huge or fine-grained. If your lengths are millimetres on a 12-metre bar, n = 12,000 and m is the number of priced lengths, which is easily fast enough. If they are arbitrary real numbers, rescale to the coarsest unit that still makes sense physically before running the DP.

The same shape shows up elsewhere. Splitting a sequence into consecutive segments with a per-segment score is rod cutting with prices that depend on position. That is the structure behind line breaking and text segmentation, and it leads to the interval DPs in matrix chain multiplication, where the cost of a piece depends on both endpoints.

Failure modes

• Greedy by density. Wrong at length 4 in our table; never ship it without a proof for your specific prices.
• Zero-initialised unreachable states. Reports revenue for rods that cannot be cut exactly. Use minus infinity, or model scrap explicitly.
• Plain recursion without memoisation. Exponential: the call count doubles with each extra unit of length.
• Charging cut cost on the uncut rod. Makes selling whole look worse than it is; the brute-force oracle catches this immediately.
• Floating-point prices. Ties break differently across platforms and reconstruction becomes unstable. Use integer cents.

What to do next

1. Implement cut_rod from memory, then run it on the price table above and confirm the best-revenue row.
2. Add the brute-force oracle and the random test; then deliberately break the inner loop bound and watch the test fail.
3. Add the cut-cost and at-most-K-pieces variants and confirm the length-4 and length-7 answers given here.
4. Change the price list so that only lengths 3 and 5 sell, and make the code report lengths that cannot be filled exactly.
5. Write down the time complexity in terms of n and m, and explain why it is pseudo-polynomial.
6. Move on to interval DPs such as matrix chain multiplication, where the cost of a piece depends on both of its ends.