Offensive Security Researcher & Quantum Cryptography Analyst

Rod Cutting Problem: Dynamic Programming Approach and Optimal Solution

Abdul Wahab Junaid
Rod Cutting Problem: Dynamic Programming Approach

When I first came across the rod cutting problem, I remember thinking it looked deceptively simple. I have a rod of a certain length, I can cut it into pieces, and each piece length has a price attached to it in a price table. My job is to figure out how to cut the rod so that I earn the maximum possible revenue. That’s it. But underneath this simple description lies one of the cleanest introductions to dynamic programming that I have ever worked through.

I find this problem important because it teaches the core intuition of dynamic programming without drowning me in complexity. It shows me how a problem with exponentially many possible solutions can be solved efficiently once I notice that it is built out of smaller versions of itself. Once I understand rod cutting, concepts like memoization, bottom-up tabulation, and optimal substructure stop feeling abstract and start feeling like tools I actually know how to use.

History and Background

The rod cutting problem is one of the standard teaching examples popularized by the textbook “Introduction to Algorithms,” written by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein — a book I keep coming back to whenever I want to relearn a classic algorithm properly. It isn’t tied to a single historical inventor the way, say, Dijkstra’s algorithm is tied to Edsger Dijkstra. Instead, it emerged as a pedagogical device, built specifically to illustrate dynamic programming in a setting that mirrors real economic decision-making: given a resource that can be divided, how do I divide it to maximize value.

Dynamic programming itself, as a general method, was developed by Richard Bellman in the 1950s while he worked at RAND Corporation. Bellman was trying to solve multistage decision problems, and he coined the term “dynamic programming” partly because it sounded impressive enough to survive bureaucratic scrutiny in his research funding. Rod cutting, as a specific application, became a natural way for later educators to demonstrate Bellman’s ideas because it is intuitive, physically visualizable, and free of unnecessary mathematical baggage.

Problem Statement

Here’s how I formally think about it. I’m given a rod of length $n$ inches and a table of prices $p_i$ for $i = 1, 2, \dots, n$, where $p_i$ is the price I get for selling a piece of rod that is $i$ inches long. I need to determine the maximum revenue $r_n$ obtainable by cutting up the rod and selling the pieces. Cutting itself is free, and I am allowed to not cut the rod at all if selling it whole gives the best price.

The tricky part is that the number of ways to cut a rod of length $n$ grows exponentially — there are $2^{n-1}$ different ways to cut it, because at each of the $n-1$ points between inches I either make a cut or I don’t. Trying every combination becomes infeasible even for a rod that is 30 or 40 inches long.

Core Concepts

Before I dive into the mechanics, I want to lay out a few terms I rely on throughout this discussion:

How It Works

I approach rod cutting by breaking it into a first-cut decision. Suppose the rod has length $n$. I imagine making my very first cut at some position, giving me a first piece of length $i$ (where $1 \le i \le n$) and a remaining rod of length $n – i$. The remaining rod then needs to be cut optimally as well, which is itself a smaller instance of the same problem.

So my job reduces to trying every possible value of $i$ from $1$ to $n$, and for each one, adding the price $p_i$ to the optimal revenue of the remaining piece, $r_{n-i}$. I then take whichever choice of $i$ gives the highest total. This is the essence of a dynamic programming recurrence — I express the answer to a big problem in terms of answers to smaller problems of the same type.

Working Principle

Internally, what makes this efficient is that I never solve the same subproblem twice. In the naive recursive version, computing $r_n$ requires computing $r_{n-1}, r_{n-2}, \dots, r_0$, but each of those calls itself branches into computing all the smaller values again. This causes an explosion of duplicate work, with a recursion tree that has exponentially many nodes.

To fix this, I keep an array, let’s call it r[], where r[j] stores the already-computed optimal revenue for a rod of length j. Whether I fill this array top-down through memoized recursion or bottom-up through iteration, the principle is the same: once a subproblem is solved, I never solve it again — I just read the stored answer.

Mathematical Foundation

The recurrence that captures the entire problem is:

$$ r_n = \max_{1 \le i \le n} (p_i + r_{n-i}) $$

with the base case:

$$ r_0 = 0 $$

This says the best revenue for a rod of length $n$ is the maximum, over all first-piece choices $i$, of the price of that first piece plus the best revenue obtainable from optimally cutting the remaining $n – i$ inches.

There’s an equivalent formulation that some textbooks prefer, which treats the uncut rod itself as one of the choices, and only considers cuts after the first piece:

$$ r_n = \max(p_n, r_1 + r_{n-1}, r_2 + r_{n-2}, \dots, r_{n-1} + r_1) $$

Both formulations are mathematically equivalent since the version I use above already accounts for “no cut” as the case where $i = n$, giving $p_n + r_0 = p_n$.

Proof sketch of optimal substructure. Suppose an optimal solution for a rod of length $n$ makes its first cut at length $i$. Then the remaining piece of length $n – i$ must itself be cut in an optimal way. If it weren’t, I could replace that portion’s cutting strategy with a better one and increase total revenue, contradicting the assumption that I started with an optimal solution. This exchange argument is the standard way I convince myself that optimal substructure holds.

Diagrams

flowchart TD
    A[Rod of length n] --> B{Try each first piece i from 1 to n}
    B --> C[Piece of length i, price p_i]
    B --> D[Remaining rod of length n - i]
    D --> E[Recursively solve r of n - i]
    C --> F[Add p_i + r of n - i]
    E --> F
    F --> G{Compare across all i}
    G --> H[Pick maximum value]
    H --> I[Store as r_n in table]

Pseudocode

I’ll present both the memoized top-down version and the bottom-up tabulated version, since together they show the two main flavors of dynamic programming.

Bottom-up (tabulation):

BOTTOM-UP-CUT-ROD(p, n)
    let r[0..n] be a new array
    r[0] = 0
    for j = 1 to n
        q = -infinity
        for i = 1 to j
            q = max(q, p[i] + r[j - i])
        r[j] = q
    return r[n]

Top-down with memoization:

MEMOIZED-CUT-ROD(p, n)
    let r[0..n] be a new array
    for i = 0 to n
        r[i] = -infinity
    return MEMOIZED-CUT-ROD-AUX(p, n, r)

MEMOIZED-CUT-ROD-AUX(p, n, r)
    if r[n] >= 0
        return r[n]
    if n == 0
        q = 0
    else
        q = -infinity
        for i = 1 to n
            q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r))
    r[n] = q
    return q

Extended version that also reconstructs the actual cuts:

EXTENDED-BOTTOM-UP-CUT-ROD(p, n)
    let r[0..n] and s[0..n] be new arrays
    r[0] = 0
    for j = 1 to n
        q = -infinity
        for i = 1 to j
            if q < p[i] + r[j - i]
                q = p[i] + r[j - i]
                s[j] = i
        r[j] = q
    return r and s

Step-by-Step Example

Let me walk through a concrete example, using the classic price table from Cormen et al. for lengths 1 through 10:

Length $i$12345678910
Price $p_i$1589101717202430

Suppose I want to cut a rod of length $n = 4$. I compute the table bottom-up:

So the maximum revenue I can get from a 4-inch rod is 10, achieved by cutting it into two 2-inch pieces (each worth 5). This matches the well-known result from the textbook example, and it’s a nice sanity check that my table-filling logic is correct.

Time Complexity

The bottom-up version has two nested loops: the outer loop runs $n$ times (for $j$ from 1 to $n$), and the inner loop runs up to $j$ times (for $i$ from 1 to $j$). This gives a total time of:

$$ \sum_{j=1}^{n} j = \Theta(n^2) $$

The memoized top-down version has the same $\Theta(n^2)$ complexity, because each of the $n+1$ subproblems is solved exactly once, and solving each one takes $O(n)$ time in the worst case due to the inner loop over choices of $i$.

Compare this to the naive recursive solution without memoization, which has exponential running time $\Theta(2^n)$, since the recursion tree branches into overlapping subproblems that get recomputed over and over. This contrast is, in my opinion, the single most convincing demonstration of why dynamic programming matters.

Space Complexity

Both the bottom-up and memoized versions use $\Theta(n)$ additional space for the r[] array that stores the optimal revenue for every subproblem length from 0 to $n$. If I also want to reconstruct the actual cuts (not just the maximum revenue), I need an additional array s[] of size $n+1$, which is still $\Theta(n)$ space, just with a larger constant factor.

The naive recursive version, interestingly, uses less space in terms of an explicit table, but its call stack can grow as deep as $\Theta(n)$ in the worst case, and it doesn’t save me any time, so it’s rarely worth the trade-off.

Correctness Analysis

I convince myself the algorithm is correct through the optimal substructure argument I outlined earlier: any optimal solution for a rod of length $n$ can be decomposed into a first piece and an optimally-cut remainder. Since my recurrence explicitly considers every possible first piece length $i$ from 1 to $n$, and for each one uses the already-correct optimal value $r_{n-i}$, the maximum over all these choices must be the true optimal value $r_n$.

The base case $r_0 = 0$ is trivially correct — a rod of length zero has no pieces to sell, so it contributes nothing. By induction on $n$, assuming $r_0, r_1, \dots, r_{n-1}$ are all correct, the recurrence guarantees $r_n$ is also correct, since it’s built directly from a complete and correctly computed set of smaller optimal values.

Advantages

Disadvantages

Applications

Whenever I explain this problem to someone new to algorithms, I like to point out that “rod cutting” is really just an alias for a much broader class of resource-allocation problems. It applies to:

Implementation in C

Here is a complete, self-contained implementation showing both the revenue computation and the reconstruction of the actual cuts:

#include <stdio.h>
#include <limits.h>

/* Computes the maximum revenue and fills the cut-choice array s[]
   so I can later reconstruct exactly how to cut the rod. */
int extendedBottomUpCutRod(int p[], int n, int r[], int s[]) {
    r[0] = 0;

    for (int j = 1; j <= n; j++) {
        int q = INT_MIN;
        for (int i = 1; i <= j; i++) {
            if (q < p[i] + r[j - i]) {
                q = p[i] + r[j - i];
                s[j] = i;   /* record the best first-piece length for this j */
            }
        }
        r[j] = q;
    }
    return r[n];
}

/* Prints the actual sequence of cut lengths that achieve the
   optimal revenue, using the s[] array filled above. */
void printCutSolution(int s[], int n) {
    printf("Optimal pieces: ");
    while (n > 0) {
        printf("%d ", s[n]);
        n = n - s[n];
    }
    printf("\n");
}

int main(void) {
    /* p[i] is the price of a piece of length i; p[0] is unused */
    int p[] = {0, 1, 5, 8, 9, 10, 17, 17, 20, 24, 30};
    int n = 10;  /* length of the rod I want to cut */

    int r[11];   /* r[j] will hold optimal revenue for length j */
    int s[11];   /* s[j] will hold the first-piece length chosen for j */

    int maxRevenue = extendedBottomUpCutRod(p, n, r, s);

    printf("Maximum revenue for rod of length %d is %d\n", n, maxRevenue);
    printCutSolution(s, n);

    return 0;
}

I want to walk through the logic briefly: r[j] always holds the best revenue for a rod of length j once the loop reaches index j, because by the time I compute r[j], every r[j-i] for i from 1 to j has already been computed in an earlier iteration. The s[j] array remembers which first-piece length produced that best revenue, so printCutSolution can walk backward through the rod, printing each piece length and shrinking the remaining rod until nothing is left.

Sample Input and Output

Using the price table and rod length from the code above:

Input:
p[] = {1, 5, 8, 9, 10, 17, 17, 20, 24, 30}  (indices 1 through 10)
n = 10

Output:
Maximum revenue for rod of length 10 is 30
Optimal pieces: 10

For a rod of length 10, it turns out the best strategy is to not cut it at all and sell it whole for 30. If I instead try $n = 7$, I get:

Input:
n = 7

Output:
Maximum revenue for rod of length 7 is 18
Optimal pieces: 1 6

This means the best strategy for a length-7 rod is to cut it into a 1-inch piece (worth 1) and a 6-inch piece (worth 17), for a total of 18, which beats selling it whole for 17.

Optimization Techniques

Common Mistakes

Further Reading

Exit mobile version