☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Rod cutting problem

Hard TUF ID 322 SDE

Java source ↗ Edit this article ↗

Problem

You have a rod of length n and an array price of length n, where price[i] is what a piece of length i + 1 sells for. You may cut the rod into any number of pieces whose lengths are positive integers adding up to n (making no cut at all is allowed). Return the maximum total selling price.

Typical constraints (GeeksforGeeks / Coding Ninjas): 1 ≤ n ≤ 1000, 1 ≤ price[i] ≤ 10^5. The answer is at most 1000 × 10^5 = 10^8, which fits in an int.

Example 1

price = [1, 5, 8, 9, 10, 17, 17, 20]      (n = 8)
answer = 22         // lengths 2 + 6 sell for 5 + 17

Example 2

price = [3, 5, 8, 9, 10, 17, 17, 20]      (n = 8)
answer = 24         // eight pieces of length 1 sell for 8 × 3

Why the obvious heuristics fail

A natural guess is to keep cutting the piece with the best price per unit length. Take price = [1, 5, 8, 9] (n = 4). Length 3 has the best ratio (8 / 3 ≈ 2.67), so greedy cuts a 3 and is left with a piece of length 1, earning 8 + 1 = 9. Two pieces of length 2 earn 5 + 5 = 10. The best-ratio length may not divide the rod, and the leftover can be nearly worthless, so the first choice and the remainder interact. We have to consider every way of cutting, but in an order that lets us reuse work.

The recurrence: what is the first piece?

Every way of cutting a rod of length len has a first piece (say, the leftmost), of some length k between 1 and len. Once that piece is fixed, the remaining rod of length len - k should be cut optimally on its own; nothing about the first piece constrains it. Trying all k therefore covers every cutting:

best(0)   = 0
best(len) = max over k = 1..len of ( price[k - 1] + best(len - k) )
answer    = best(n)

k = len means “sell the whole remaining rod as one piece”, so “no cut” is included.

Approach 1: Recursion

Intuition. Implement best(len) directly. Each call loops over all first-piece lengths and recurses on the remainder.

Algorithm.

  1. If len == 0, return 0.
  2. For each k from 1 to len, compute price[k - 1] + best(len - k) and keep the maximum.
  3. Return the maximum.
static int recursion(int[] price) {
    return best(price.length, price);
}

static int best(int len, int[] price) {
    if (len == 0) return 0;                                  // nothing left to sell
    int result = 0;
    for (int k = 1; k <= len; k++) {                         // first piece has length k
        result = Math.max(result, price[k - 1] + best(len - k, price));
    }
    return result;
}

Complexity. Time O(2^n). Every way of writing n as an ordered sum of positive integers is visited, and there are 2^(n - 1) of them (each of the n - 1 gaps is either cut or not). Space O(n) for the stack.

The waste is obvious: best(3) is recomputed after a first piece of 5, after pieces of 4 then 1, after 1 then 4, and so on.

Approach 2: Memoization

Intuition. best has a single argument, len, which takes only n + 1 values. Store each result in dp[len] and reuse it. Since prices are non-negative, every real answer is ≥ 0, so -1 marks “not computed”.

Algorithm.

  1. Allocate dp[n + 1] filled with -1.
  2. Run the recursion, returning dp[len] if it is filled, and saving the result otherwise.
static int memoization(int[] price) {
    int[] dp = new int[price.length + 1];
    Arrays.fill(dp, -1);
    return memo(price.length, price, dp);
}

static int memo(int len, int[] price, int[] dp) {
    if (len == 0) return 0;
    if (dp[len] != -1) return dp[len];
    int result = 0;
    for (int k = 1; k <= len; k++) {
        result = Math.max(result, price[k - 1] + memo(len - k, price, dp));
    }
    return dp[len] = result;
}

Complexity. Time O(n^2): n states, each looping over up to n first pieces. Space O(n) for the table and the stack.

Approach 3: Tabulation

Intuition. best(len) only reads strictly shorter lengths, so filling best[1], best[2], ..., best[n] in increasing order guarantees every value we read is final. No recursion, no stack.

Algorithm.

  1. best[0] = 0.
  2. For len from 1 to n, for k from 1 to len: best[len] = max(best[len], price[k - 1] + best[len - k]).
  3. Return best[n].
static int tabulation(int[] price) {
    int n = price.length;
    int[] best = new int[n + 1];                             // best[len]: maximum value for a rod of length len
    for (int len = 1; len <= n; len++) {
        for (int k = 1; k <= len; k++) {
            best[len] = Math.max(best[len], price[k - 1] + best[len - k]);
        }
    }
    return best[n];
}

Dry run on price = [2, 5, 7, 8] (n = 4):

len candidates price[k-1] + best[len-k] for k = 1..len best[len]
1 2 + 0 2
2 2 + 2, 5 + 0 5
3 2 + 5, 5 + 2, 7 + 0 7
4 2 + 7, 5 + 5, 7 + 2, 8 + 0 10

Complexity. Time O(n^2). Space O(n), which is already minimal for this formulation, so there is no separate space-optimised step.

The knapsack view

Many courses present the same problem as an unbounded knapsack: the “items” are piece lengths 1..n, piece k has weight k and value price[k - 1], each can be used any number of times, and the capacity is n. The state becomes (i, len) (“using piece lengths up to i + 1, fill len”), with the transitions “never use length i + 1 again” and “use one more piece of length i + 1”:

f(i, len) = max( f(i - 1, len),  price[i] + f(i, len - (i + 1)) )   if i + 1 ≤ len

It reaches the same answer with the same O(n^2) time, and after space optimisation it is also a single array of size n + 1. The first-piece recurrence above is simply the knapsack table collapsed: because the capacity (n) and the number of item types (n) coincide, we can loop over the item inside each length instead of the other way round. Both orders work for maximisation; the order matters only when counting combinations, as in coin change.

Edge cases and pitfalls