Rod Cutting Problem — O(2^n) Crashes After n=35

Every compiler that packs instructions into cache lines, every stock trader slicing a large order into smaller trades, every furniture manufacturer deciding how to cut timber to minimize waste — they're all solving variations of the same fundamental optimization question: given a resource you can divide, what's the most valuable partition? The rod cutting problem is the canonical formulation of that question, and it sits at the intersection of combinatorics and optimization in a way that makes it a perfect vehicle for understanding dynamic programming at depth.

What is Rod Cutting? — Plain English

The Rod Cutting problem: given a rod of length n and a price table where price[i] is the value of a piece of length i, determine the maximum revenue obtainable by cutting the rod and selling the pieces. Pieces can be sold in any combination. You choose how many cuts to make and where.

Example: a rod of length 4 with prices [0, 2, 5, 7, 8] (price[1]=2, price[2]=5, price[3]=7, price[4]=8). Selling as two pieces of length 2 yields 5+5=10, better than the unsplit price of 8.

How Rod Cutting Works — Step by Step

Define dp[i] = maximum revenue from a rod of length i.

1. dp[0] = 0 (zero-length rod has zero value).
2. For each length i from 1 to n:
3. For each first cut at length j from 1 to i:
4. dp[i] = max(dp[i], price[j] + dp[i - j])
5. (price[j] is the value of selling a piece of length j; dp[i-j] is the optimal value of the remainder)
6. Return dp[n].

Time: O(n^2). Space: O(n).

Worked Example — Tracing the Algorithm

Rod length n=4. Prices: price[1]=2, price[2]=5, price[3]=7, price[4]=8.

dp[0]=0.

dp[1]: try j=1: price[1]+dp[0]=2+0=2. dp[1]=2.

dp[2]: try j=1: price[1]+dp[1]=2+2=4. try j=2: price[2]+dp[0]=5+0=5. dp[2]=max(4,5)=5.

dp[3]: try j=1: price[1]+dp[2]=2+5=7. try j=2: price[2]+dp[1]=5+2=7. try j=3: price[3]+dp[0]=7+0=7. dp[3]=7.

dp[4]: try j=1: price[1]+dp[3]=2+7=9. try j=2: price[2]+dp[2]=5+5=10. try j=3: price[3]+dp[1]=7+2=9. try j=4: price[4]+dp[0]=8+0=8. dp[4]=max(9,10,9,8)=10.

Maximum revenue for length-4 rod = 10 (cut into two pieces of length 2).

Implementation — Java

The following Java implementation demonstrates rod cutting with both top-down memoization and bottom-up tabulation. The code is ready for production use with proper edge case handling.

package io.thecodeforge;

public class RodCutting {
    public static int bottomUp(int[] prices, int n) {
        int[] dp = new int[n + 1];
        dp[0] = 0;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = Math.max(dp[i], prices[j] + dp[i - j]);
            }
        }
        return dp[n];
    }

    public static int topDown(int[] prices, int n) {
        Integer[] memo = new Integer[n + 1];
        return helper(prices, n, memo);
    }

    private static int helper(int[] prices, int n, Integer[] memo) {
        if (n == 0) return 0;
        if (memo[n] != null) return memo[n];
        int max = 0;
        for (int j = 1; j <= n; j++) {
            max = Math.max(max, prices[j] + helper(prices, n - j, memo));
        }
        memo[n] = max;
        return max;
    }
}

Reconstructing the Cuts — Which Pieces to Sell

The DP only tells you the maximum revenue, not which cuts yield it. To know the actual cutting plan, maintain a 'firstCut' array where firstCut[i] stores the length of the first piece in the optimal solution for rod length i. After computing dp, trace back from n to 0.

Algorithm: 1. Initialize firstCut[0] = 0. 2. In the inner loop, when dp[i] is updated with price[j] + dp[i-j], record firstCut[i] = j. 3. To reconstruct: start at i = n, while i > 0: print firstCut[i]; i -= firstCut[i].

For the example: firstCut[1]=1, firstCut[2]=2, firstCut[3]=1 (or 3, tie-breaking can go to any), firstCut[4]=2. Tracing: i=4 → cut length 2, i=2 → cut length 2, i=0 stop. Pieces: [2,2].

Variations and Production Considerations

Rod cutting is a direct analog of the unbounded knapsack problem: each piece length is an 'item' with weight = length and value = price, and you can take unlimited copies (since multiple pieces of the same length are allowed).

Production pattern: When the price list follows a known function (e.g., linear with discounts for longer pieces), the DP can be replaced with a greedy algorithm or a formula — test for this before using DP blindly.

Using Recursion – The Baseline You Shouldn't Ship

Before we get to the good stuff, let's look at the raw recursive approach. It's the naive solution interviewers expect you to mention before you show them something better.

The idea is brutally simple: for a rod of length i, try every possible first cut j from 1 to i. The revenue is price[j] plus whatever you can get from the remaining length i - j. Take the max. That's it.

The recursion tree explodes. For each length i, you branch into i possibilities. That gives you O(2^n) time. For n=10 you're fine. For n=30 you're waiting minutes. For n=50 the heat death of the universe becomes a concern.

Why waste time on this? Because it's the clearest expression of the problem's structure. Every DP solution is just this recursion with caching or iteration — same logic, no recomputation. Understand this first, then optimise.

// io.thecodeforge — dsa tutorial

public class RodCutRecursive {
    public static int cutRod(int[] price, int n) {
        // base case: rod of length 0 yields nothing
        if (n == 0) return 0;
        int best = 0;
        // try every possible first cut
        for (int cut = 1; cut <= n; cut++) {
            int revenue = price[cut] + cutRod(price, n - cut);
            if (revenue > best) best = revenue;
        }
        return best;
    }

    public static void main(String[] args) {
        int[] price = {0, 1, 5, 8, 9, 10, 17, 17, 20};
        int rodLen = price.length - 1;
        System.out.println(cutRod(price, rodLen));
    }
}

Top-Down DP (Memoization) – The Pragmatic Fix

Same recursion, one tweak: cache results. That's it. The only difference from the naive version is you check if you've already computed cutRod(i) before recursing. If yes, return the cached value. No recomputation, no branches you've already explored.

This drops complexity from O(2^n) to O(n^2). Why n^2? For each of n lengths, you consider n possible cuts. The memoisation ensures each subproblem is solved exactly once.

Space is O(n) for the cache array. Plus O(n) for the call stack if you recurse deep — which hits stack overflow for n > ~10k in Java. That's why bottom-up is safer, but for interview or prototyping clarity, top-down is king.

The pattern: if you can write the recursion, you can memoise it. No new theory. Just add a lookup table and a guard clause. Every production DP I've written started as memoised recursion before getting refactored to tabulation for performance.

// io.thecodeforge — dsa tutorial

import java.util.Arrays;

public class RodCutMemo {
    public static int cutRod(int[] price, int n, int[] memo) {
        if (n == 0) return 0;
        if (memo[n] != -1) return memo[n];  // cached
        int best = 0;
        for (int cut = 1; cut <= n; cut++) {
            int revenue = price[cut] + cutRod(price, n - cut, memo);
            if (revenue > best) best = revenue;
        }
        memo[n] = best;
        return best;
    }

    public static void main(String[] args) {
        int[] price = {0, 1, 5, 8, 9, 10, 17, 17, 20};
        int n = price.length - 1;
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        System.out.println(cutRod(price, n, memo));
    }
}