☕ DSA Java Articles

Topics › Dynamic Programming › DP on Subsequences

Rod Cutting Problem - (DP - 24)

Hard TUF ID 2803 A2Z

Java source ↗ Edit this article ↗

Problem

You have a rod of length n and an array price of length n, where price[i] is the selling price of a piece of length i + 1. You may cut the rod into any number of pieces of integer length (or not cut it at all), and you may cut the same length as many times as you like. Return the maximum total price you can get for the pieces.

Constraints: 1 ≤ n ≤ 1000, 0 ≤ price[i] ≤ 10^5. The answer is at most 1000 × 10^5 = 10^8, so it fits in an int.

Example 1

price = [2, 5, 7, 8, 10]          // lengths 1..5, rod length 5
answer = 12                       // 2 + 2 + 1 sells for 5 + 5 + 2 (2 + 3 also gives 5 + 7)

Example 2

price = [3, 5, 8, 9, 10, 17, 17, 20]
answer = 24                       // eight pieces of length 1: 8 × 3

Recognising the pattern

Think of every piece length L = i + 1 as an item with weight L and value price[i], and of the rod as a knapsack of capacity n. Choosing pieces whose lengths add up to n is choosing items whose weights add up to the capacity. Two details pin down which knapsack this is:

Greedy does not work. With price = [0, 5, 8, 0] the best price per unit is length 3 (8 / 3 ≈ 2.67), but cutting 3 + 1 earns only 8, while 2 + 2 earns 10. The best choice for one piece depends on what the rest of the rod can earn, which is exactly what DP tracks.

Approach 1: Recursion

Intuition. Let f(ind, len) be the best price for a rod of length len when only piece lengths 1 .. ind + 1 are allowed. Look at the largest allowed length, ind + 1:

When ind == 0 only length 1 is allowed, so the rod is cut into len unit pieces worth len * price[0].

Deciding lengths in a fixed order (largest index first) means each multiset of pieces is explored once; the order in which cuts are made does not matter for the total.

Algorithm.

  1. If ind == 0, return len * price[0].
  2. notTake = f(ind - 1, len).
  3. If ind + 1 ≤ len, take = price[ind] + f(ind, len - (ind + 1)); otherwise take = -∞.
  4. Return max(take, notTake). The answer is f(n - 1, n).
static int recursive(int[] price) {
    int n = price.length;
    return solve(n - 1, n, price);
}

/** Best value for a rod of length len using only piece lengths 1 .. ind + 1. */
static int solve(int ind, int len, int[] price) {
    if (ind == 0) return len * price[0];                 // only length-1 pieces remain: cut len of them
    int notTake = solve(ind - 1, len, price);
    int take = Integer.MIN_VALUE;
    int pieceLen = ind + 1;
    if (pieceLen <= len) take = price[ind] + solve(ind, len - pieceLen, price);  // stay at ind: unlimited supply
    return Math.max(take, notTake);
}

Complexity. Time is exponential: every call branches twice, and the take branch does not decrease ind, so the tree can be larger than 2^n. Space O(n) for the stack: every call either lowers ind or lowers len by at least 2.

Approach 2: Memoization

Intuition. The state is just the pair (ind, len), with n choices for ind and n + 1 for len. Different cut sequences reach the same state constantly (cutting 2 then 3 and cutting 3 then 2 both leave len - 5), so caching each state’s answer removes all repeated work. Prices are non-negative, so -1 safely marks “not computed”.

Algorithm.

  1. Create dp[n][n + 1] filled with -1.
  2. Same recursion; return dp[ind][len] if already set, otherwise compute it, store it, and return it.
static int memoization(int[] price) {
    int n = price.length;
    int[][] dp = new int[n][n + 1];
    for (int[] row : dp) Arrays.fill(row, -1);
    return memo(n - 1, n, price, dp);
}

static int memo(int ind, int len, int[] price, int[][] dp) {
    if (ind == 0) return len * price[0];
    if (dp[ind][len] != -1) return dp[ind][len];
    int notTake = memo(ind - 1, len, price, dp);
    int take = Integer.MIN_VALUE;
    int pieceLen = ind + 1;
    if (pieceLen <= len) take = price[ind] + memo(ind, len - pieceLen, price, dp);
    return dp[ind][len] = Math.max(take, notTake);
}

Complexity. Time O(n^2): n × (n + 1) states, each doing constant work. Space O(n^2) for the table plus O(n) stack.

Approach 3: Tabulation

Intuition. f(ind, len) reads row ind - 1 (not take) and row ind at a smaller length (take). So fill rows in increasing ind, and within a row fill lengths from small to large. The base row ind = 0 is len * price[0] for every len.

Algorithm.

  1. dp[0][len] = len * price[0] for len = 0 .. n.
  2. For ind = 1 .. n - 1 and len = 0 .. n: notTake = dp[ind - 1][len]; if the piece fits, take = price[ind] + dp[ind][len - (ind + 1)]; store the larger.
  3. Return dp[n - 1][n].
static int tabulation(int[] price) {
    int n = price.length;
    int[][] dp = new int[n][n + 1];
    for (int len = 0; len <= n; len++) dp[0][len] = len * price[0];   // base case: only length-1 pieces
    for (int ind = 1; ind < n; ind++) {
        int pieceLen = ind + 1;
        for (int len = 0; len <= n; len++) {
            int notTake = dp[ind - 1][len];
            int take = Integer.MIN_VALUE;
            if (pieceLen <= len) take = price[ind] + dp[ind][len - pieceLen];
            dp[ind][len] = Math.max(take, notTake);
        }
    }
    return dp[n - 1][n];
}

Complexity. Time O(n^2), space O(n^2).

Approach 4: Space optimized

Intuition. The usual next step keeps two rows, prev and cur. Here we can go further and keep one array. Look at what the update for best[len] needs:

So an in-place left-to-right sweep computes the recurrence exactly. (In 0/1 knapsack, take needs the previous row instead, which is why that version must sweep right to left.) Lengths smaller than pieceLen cannot use the piece and keep their value, so the loop starts at pieceLen.

Algorithm.

  1. best[len] = len * price[0] for all len.
  2. For each ind = 1 .. n - 1, for len = ind + 1 .. n: best[len] = max(best[len], price[ind] + best[len - (ind + 1)]).
  3. Return best[n].
static int spaceOptimized(int[] price) {
    int n = price.length;
    int[] best = new int[n + 1];
    for (int len = 0; len <= n; len++) best[len] = len * price[0];
    for (int ind = 1; ind < n; ind++) {
        int pieceLen = ind + 1;
        for (int len = pieceLen; len <= n; len++) {
            best[len] = Math.max(best[len], price[ind] + best[len - pieceLen]);  // best[len - pieceLen] is already this row
        }
    }
    return best[n];
}

Dry run on Example 1, price = [2, 5, 7, 8, 10]:

after piece length best[0..5]
1 (price 2) [0, 2, 4, 6, 8, 10]
2 (price 5) [0, 2, 5, 7, 10, 12]
3 (price 7) [0, 2, 5, 7, 10, 12]
4 (price 8) [0, 2, 5, 7, 10, 12]
5 (price 10) [0, 2, 5, 7, 10, 12]

During the length-2 pass, best[4] = max(8, 5 + best[2]) = 10 uses best[2] = 5, which was set moments earlier in the same pass; that is two length-2 pieces. The answer is best[5] = 12.

Complexity. Time O(n^2), space O(n).

Edge cases and pitfalls