How to solve the rod cutting problem with dynamic programming

The rod cutting problem is a classic optimisation exercise: given a rod of a fixed length and a price for every possible piece length, determine how to cut the rod for maximum revenue. It looks simple at first, but the number of possible cutting patterns grows rapidly as the rod becomes longer. Learn more about About.

Dynamic programming turns this large search into a sequence of smaller decisions. The same idea appears in stock planning, timber processing, budgeting, and many programming interview problems. Whether you are studying algorithms in Melbourne, preparing for a coding interview in Sydney, or practising Python on a rainy Brisbane arvo, this problem is a useful way to build intuition about overlapping subproblems.

Approach	Main idea	Time complexity	Extra space	Best use
Brute force recursion	Try every possible first cut	Exponential	O(n) stack	Understanding the search space
Memoised recursion	Cache each solved length	O(n²)	O(n)	Top-down dynamic programming
Bottom-up dynamic programming	Build answers from length 0 to n	O(n²)	O(n)	Clear and reliable implementation
Greedy cutting	Choose the locally best-looking cut	Usually fast	O(1)	Only when a proof supports it

Understanding the cutting decision

Assume a rod has length n. The input array price stores the selling price for each length, so price[1] is the value of a one-unit piece, price[2] is the value of a two-unit piece, and so on. The goal is to choose cuts whose lengths add up to n while maximising the total price.

For a rod of length 4, possible plans include keeping it whole, cutting it into lengths 1 and 3, splitting it into 2 and 2, or using four pieces of length 1. A plan may contain repeated lengths, and making no cut is a valid option. If a Melbourne timber workshop can sell a four-metre board for $10 but can earn $13 by selling two shorter pieces, the algorithm should discover that combination rather than assume the longest piece is best.

The key question is the first cut. If the first piece has length i, the remaining rod has length n - i. Once that first piece is selected, the remaining section is exactly the same type of problem, just smaller. This repeated structure is what makes dynamic programming appropriate.

Deriving the recurrence

Let best[length] represent the maximum revenue obtainable from a rod of a particular length. The empty rod has no value, so:

best[0] = 0

For every possible first cut i from 1 through length, the revenue is the price of that piece plus the best revenue for the remainder:

best[length] = max(
    price[i] + best[length - i]
    for i in 1..length
)

The recurrence checks every first cut, but it does not repeatedly solve the remainder from scratch. For example, when calculating best[6], the value of best[3] has already been computed and stored. This is the overlapping-subproblem property: many different cutting patterns ask for the answer to the same smaller rod length.

A greedy strategy can fail. Suppose a length-3 piece has a strong price and seems attractive, but two length-2 pieces produce more revenue for a length-4 rod. Choosing the most profitable individual piece does not guarantee the best total result. Dynamic programming evaluates the complete combination, which is why it is dependable for arbitrary price lists.

Building the solution from the bottom up

The bottom-up method creates an array with n + 1 entries. It starts with the empty rod and then solves lengths 1, 2, 3, up to n. At the time best[length] is calculated, every smaller value needed by the recurrence is already available.

The pseudocode is:

best[0] = 0

for length from 1 to n:
    best[length] = 0

    for first_cut from 1 to length:
        candidate = price[first_cut] + best[length - first_cut]
        best[length] = max(best[length], candidate)

return best[n]

For a rod of length 4 with prices [1, 5, 8, 9], the values become:

best[0] = 0
best[1] = 1
best[2] = 5
best[3] = 8
best[4] = 10

The result is 10, produced by two pieces of length 2. Notice that the value for length 4 is not necessarily the price of the uncut rod, which is 9. The algorithm compares every possible first cut, including a piece of length 4 itself.

Implementing the algorithm in Python

A direct Python implementation uses nested loops. The outer loop selects the rod length currently being solved, and the inner loop tries every possible first piece. Initialising the best value to zero is safe when prices are non-negative.

def rod_cutting(prices, length):
    best = [0] * (length + 1)

    for current_length in range(1, length + 1):
        maximum = 0

        for first_cut in range(1, current_length + 1):
            value = prices[first_cut - 1] + best[current_length - first_cut]
            maximum = max(maximum, value)

        best[current_length] = maximum

    return best[length]


prices = [1, 5, 8, 9]
print(rod_cutting(prices, 4))  # 10

The first_cut - 1 expression is needed because Python lists use zero-based indexing. A rod piece of length 1 is stored at prices[0], while a piece of length 4 is stored at prices[3].

If you are moving from Python to lower-level implementation, the same array-based reasoning applies in C. The C programming guide can help with arrays, loops, and memory details that matter when translating this algorithm. In production code, validate that length does not exceed the number of available prices, or define how missing prices should be handled.

Tracking the actual cuts

The maximum revenue alone may not be enough. A timber supplier, furniture maker, or logistics system may need to know which pieces to produce. To recover the cutting plan, store the first cut that gave the best value for each length.

def rod_cutting_with_cuts(prices, length):
    best = [0] * (length + 1)
    first_piece = [0] * (length + 1)

    for current_length in range(1, length + 1):
        for piece in range(1, current_length + 1):
            value = prices[piece - 1] + best[current_length - piece]

            if value > best[current_length]:
                best[current_length] = value
                first_piece[current_length] = piece

    cuts = []
    remaining = length

    while remaining > 0:
        piece = first_piece[remaining]
        cuts.append(piece)
        remaining -= piece

    return best[length], cuts

For the price list [1, 5, 8, 9] and length 4, the function returns revenue 10 and cuts [2, 2]. Ties can be handled in different ways: keep the first solution found, prefer fewer pieces, or prefer longer pieces. The correct rule depends on the business requirement.

In an Australian setting, that extra information could represent timber lengths loaded onto a ute for delivery between a workshop and a building site. Physical constraints may then matter: a saw may have a fixed kerf, some lengths may be unavailable, and a customer may place a minimum order. Those conditions require adjusting the state or the price model rather than quietly assuming every cut is possible.

Analysing performance and extending the model

There are n outer-loop iterations, and the inner loop performs at most n checks for each one. Therefore, the bottom-up algorithm runs in O(n²) time and uses O(n) additional space. This is far better than the exponential brute-force recurrence, which explores nearly every possible sequence of cuts.

The method is closely related to unbounded knapsack. Each piece length can be selected repeatedly, its “weight” is its length, and its “value” is its price. That connection helps when recognising similar problems in coding assessments. For comparison, understanding complexity in other algorithmic approaches, such as Shell sort analysis, reinforces why asymptotic growth matters even when a small test case runs quickly.

Several practical variations are common. Add a fixed cost per cut by subtracting that cost whenever a new piece is created. Restrict the number of cuts by adding another state dimension. Allow negative prices only if the problem explicitly permits them, and initialise values carefully in that case rather than relying on zero. For unusually large inputs, rolling arrays usually do not help because each state depends on many earlier lengths, but careful validation and efficient input handling still improve real performance.

The rod cutting problem demonstrates the central dynamic programming pattern: define a state, identify the smaller states it depends on, choose a base case, and record the best decision. Once best[0] through best[n] are filled, the answer for the complete rod is simply best[n], with the optional predecessor array revealing the exact cutting plan.