Skip to main content
CodePeetCodePeet
CodePeet 444 Complete DSA Sheet

Rod Cutting

HARDProblemSolveExternal Links

Description

You are given a rod of length n inches along with an array price[], where price[i] represents the selling price of a piece of length i (1-indexed). Note that n equals the size of the price array.

Your task is to determine the maximum revenue you can obtain by cutting the rod into pieces of integer lengths and selling those pieces. You may cut the rod into any number of pieces (including keeping it whole), and each piece length from 1 to n can be used any number of times.

Return a single integer representing the maximum obtainable revenue.

Examples

Example 1

Input: price = [2, 5, 7, 8]

Output: 10

Explanation: The rod has length 4. Consider all ways to cut it:

  • No cut: sell as length 4 → price[4] = 8
  • Cut into 1+3: price[1] + price[3] = 2 + 7 = 9
  • Cut into 2+2: price[2] + price[2] = 5 + 5 = 10
  • Cut into 1+1+2: price[1] + price[1] + price[2] = 2 + 2 + 5 = 9
  • Cut into 1+1+1+1: 4 × price[1] = 4 × 2 = 8

The maximum is 10, achieved by cutting into two pieces of length 2.

Example 2

Input: price = [1, 5, 8, 9, 10, 17, 17, 20]

Output: 22

Explanation: The rod has length 8. The optimal strategy is to cut it into pieces of lengths 2 and 6: price[2] + price[6] = 5 + 17 = 22. Selling the entire rod as length 8 yields only 20, and other combinations like four pieces of length 2 (4 × 5 = 20) or two pieces of length 4 (2 × 9 = 18) produce less.

Example 3

Input: price = [3]

Output: 3

Explanation: The rod has length 1. The only option is to sell it as a single piece of length 1 for a price of 3. No further cutting is possible.

Constraints

  • 1 ≤ price.size() ≤ 10^3
  • 1 ≤ price[i] ≤ 10^6

Editorial

Brute Force

Intuition

Imagine you are a carpenter with a wooden plank. You can make a cut at any integer position along the plank, sell the pieces at their listed prices, and you want to maximize your earnings.

The most straightforward strategy is to try every possible first cut, then recursively find the best way to cut the remaining piece. For a rod of length n, the first cut can produce a piece of length 1, 2, 3, ..., or n (no cut). For each choice of first piece length j, you earn price[j] from that piece and then face the same problem with the remaining rod of length n - j.

This gives us a clean recursive formulation:

cutRod(n) = max over j = 1 to n of { price[j] + cutRod(n - j) }

Base case: cutRod(0) = 0 — a rod of length 0 earns nothing.

Unlike the knapsack where you choose items, here the "items" are the cut lengths 1 through n, each available unlimited times. At each recursive call, you try all possible cut lengths and pick the one that maximizes total revenue.

Step-by-Step Explanation

Let's trace through with price = [2, 5, 7, 8] (rod length n = 4):

Step 1: Call cutRod(4). We try all first-cut lengths j = 1, 2, 3, 4.

Step 2: j = 1: sell piece of length 1 for price[1] = 2. Remaining: cutRod(3). Need to solve cutRod(3) first.

Step 3: cutRod(3): try j = 1: 2 + cutRod(2). Need cutRod(2).

Step 4: cutRod(2): try j = 1: 2 + cutRod(1). Need cutRod(1).

Step 5: cutRod(1): only j = 1: price[1] + cutRod(0) = 2 + 0 = 2. Result: cutRod(1) = 2.

Step 6: Back to cutRod(2): j = 1 gave 2 + cutRod(1) = 2 + 2 = 4. Now j = 2: price[2] + cutRod(0) = 5 + 0 = 5. cutRod(2) = max(4, 5) = 5.

Step 7: Back to cutRod(3): j = 1 gave 2 + cutRod(2) = 2 + 5 = 7. j = 2: price[2] + cutRod(1) = 5 + 2 = 7. But wait — cutRod(1) was already computed above, yet without caching, we recompute it!

Step 8: cutRod(3): j = 3: price[3] + cutRod(0) = 7 + 0 = 7. cutRod(3) = max(7, 7, 7) = 7.

Step 9: Back to cutRod(4): j = 1 gave 2 + cutRod(3) = 2 + 7 = 9.

Step 10: cutRod(4): j = 2: price[2] + cutRod(2) = 5 + 5 = 10. cutRod(2) is recomputed again!

Step 11: cutRod(4): j = 3: price[3] + cutRod(1) = 7 + 2 = 9. cutRod(1) recomputed a third time!

Step 12: cutRod(4): j = 4: price[4] + cutRod(0) = 8 + 0 = 8. cutRod(4) = max(9, 10, 9, 8) = 10.

Notice the redundant recomputations: cutRod(1) was solved 3 times, cutRod(2) was solved 2 times.

Rod Cutting — Recursive Exploration with Redundant Calls — Watch how the recursion tries every possible first cut, diving deep before backtracking. Notice how cutRod(1) and cutRod(2) are recomputed multiple times.

Algorithm

  1. Define cutRod(n) that returns the maximum revenue for a rod of length n.
  2. Base case: If n == 0, return 0 (no rod, no revenue).
  3. Initialize maxProfit = 0.
  4. For each possible first cut length j from 1 to n:
    • Compute revenue = price[j] + cutRod(n - j)
    • Update maxProfit = max(maxProfit, revenue)
  5. Return maxProfit.
  6. The answer is cutRod(n) where n = price.size().

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int cutRodRecur(int n, vector<int>& price) {
        if (n == 0) return 0;

        int maxProfit = 0;
        for (int j = 1; j <= n; j++) {
            maxProfit = max(maxProfit, price[j - 1] + cutRodRecur(n - j, price));
        }

        return maxProfit;
    }

    int cutRod(vector<int>& price) {
        return cutRodRecur(price.size(), price);
    }
};
class Solution:
    def cutRodRecur(self, n, price):
        if n == 0:
            return 0

        max_profit = 0
        for j in range(1, n + 1):
            max_profit = max(max_profit, price[j - 1] + self.cutRodRecur(n - j, price))

        return max_profit

    def cutRod(self, price):
        return self.cutRodRecur(len(price), price)
class Solution {
    int cutRodRecur(int n, int[] price) {
        if (n == 0) return 0;

        int maxProfit = 0;
        for (int j = 1; j <= n; j++) {
            maxProfit = Math.max(maxProfit, price[j - 1] + cutRodRecur(n - j, price));
        }

        return maxProfit;
    }

    int cutRod(int[] price) {
        return cutRodRecur(price.length, price);
    }
}

Complexity Analysis

Time Complexity: O(2^n)

Let T(n) be the number of calls for a rod of length n. The recurrence is T(n) = T(n-1) + T(n-2) + ... + T(0) + 1, which solves to T(n) = 2^n. For each rod length, we try all n possible cuts, and each cut creates a recursive subproblem. Without memoization, the same subproblems are recomputed exponentially many times.

Space Complexity: O(n)

The maximum recursion depth is n (cutting length-1 pieces all the way down). Each recursive call uses O(1) stack space, so total stack space is O(n).

Why This Approach Is Not Efficient

The brute force computes 2^n recursive calls for a rod of length n. With n up to 1000, that is approximately 10^301 calls — astronomically beyond any computer's capability.

The inefficiency stems from overlapping subproblems. As we saw in the trace, cutRod(1) was computed 3 times and cutRod(2) was computed 2 times for just n = 4. For larger n, the redundancy grows exponentially. cutRod(k) is called from every cutRod(m) where m > k, at every cut position that leaves remainder k.

Yet there are only n + 1 unique subproblems: cutRod(0), cutRod(1), ..., cutRod(n). Each subproblem takes O(n) work to solve (trying all cut positions). If we store each result after the first computation, total work drops from O(2^n) to O(n²). This is exactly what memoization provides.

Better Approach - Memoization (Top-Down DP)

Intuition

Memoization applies a simple optimization to the brute force: remember every subproblem you solve. We create a 1D cache array memo[] where memo[i] stores the maximum revenue for a rod of length i.

The recursion works identically to the brute force. The only additions are:

  1. Before computing: Check if memo[n] already has a result. If yes, return it immediately (cache hit).
  2. After computing: Store the result in memo[n] before returning.

This guarantees each of the n+1 subproblems is solved exactly once. Since solving cutRod(i) tries i cut positions (O(i) work), and we solve subproblems for i = 0 to n, the total work is 1 + 2 + ... + n = O(n²).

The key insight: the recursion naturally decomposes the problem top-down, but with memoization, each subproblem's result is computed once and reused for all future references.

Step-by-Step Explanation

Let's trace with price = [2, 5, 7, 8] using a memo array initialized to [-1, -1, -1, -1, -1] (indices 0 to 4, with memo[0] = 0 as base case).

Step 1: Call cutRod(4). memo[4] = -1, uncomputed. Need cutRod(3) for j=1. memo[3] = -1. Descend.

Step 2: cutRod(3) needs cutRod(2) for j=1. memo[2] = -1. Descend.

Step 3: cutRod(2) needs cutRod(1) for j=1. memo[1] = -1. Descend.

Step 4: cutRod(1): j=1: price[1] + cutRod(0) = 2 + 0 = 2. Store memo[1] = 2.

Step 5: Back to cutRod(2): j=1: 2 + memo[1] = 2 + 2 = 4. j=2: 5 + memo[0] = 5. Store memo[2] = max(4, 5) = 5.

Step 6: Back to cutRod(3): j=1: 2 + memo[2] = 7. j=2: 5 + memo[1] = 7. ← Cache hit! memo[1] is already 2. j=3: 7 + memo[0] = 7. Store memo[3] = 7.

Step 7: Back to cutRod(4): j=1: 2 + memo[3] = 9. j=2: 5 + memo[2] = 10. ← Cache hit! No recomputation of cutRod(2).

Step 8: cutRod(4): j=3: 7 + memo[1] = 9. ← Another cache hit! j=4: 8 + memo[0] = 8. Store memo[4] = max(9, 10, 9, 8) = 10.

Answer: 10. Every subproblem was solved exactly once — memo[1]=2, memo[2]=5, memo[3]=7, memo[4]=10.

Memoization — Recursive Descent with Caching — Watch how the recursion descends to the smallest subproblem, solves it, and caches the result. Subsequent lookups of the same subproblem are instant cache hits.

Algorithm

  1. Create a memo array of size n + 1, initialized to -1. Set memo[0] = 0.
  2. Define cutRod(n) recursively:
    • If n == 0, return 0.
    • If memo[n] != -1, return memo[n] (cached result).
    • For each cut length j from 1 to n, compute revenue = price[j] + cutRod(n - j).
    • Store and return memo[n] = max of all revenues.
  3. The answer is cutRod(n) where n = price.size().

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int cutRodRecur(int n, vector<int>& price, vector<int>& memo) {
        if (n == 0) return 0;
        if (memo[n] != -1) return memo[n];

        int maxProfit = 0;
        for (int j = 1; j <= n; j++) {
            maxProfit = max(maxProfit, price[j - 1] + cutRodRecur(n - j, price, memo));
        }

        return memo[n] = maxProfit;
    }

    int cutRod(vector<int>& price) {
        int n = price.size();
        vector<int> memo(n + 1, -1);
        return cutRodRecur(n, price, memo);
    }
};
class Solution:
    def cutRodRecur(self, n, price, memo):
        if n == 0:
            return 0
        if memo[n] != -1:
            return memo[n]

        max_profit = 0
        for j in range(1, n + 1):
            max_profit = max(max_profit, price[j - 1] + self.cutRodRecur(n - j, price, memo))

        memo[n] = max_profit
        return max_profit

    def cutRod(self, price):
        n = len(price)
        memo = [-1] * (n + 1)
        return self.cutRodRecur(n, price, memo)
import java.util.Arrays;

class Solution {
    int cutRodRecur(int n, int[] price, int[] memo) {
        if (n == 0) return 0;
        if (memo[n] != -1) return memo[n];

        int maxProfit = 0;
        for (int j = 1; j <= n; j++) {
            maxProfit = Math.max(maxProfit, price[j - 1] + cutRodRecur(n - j, price, memo));
        }

        return memo[n] = maxProfit;
    }

    int cutRod(int[] price) {
        int n = price.length;
        int[] memo = new int[n + 1];
        Arrays.fill(memo, -1);
        return cutRodRecur(n, price, memo);
    }
}

Complexity Analysis

Time Complexity: O(n²)

There are n + 1 unique subproblems (rod lengths 0 through n). Each subproblem cutRod(i) tries i cut positions, doing O(1) work per cut. Total work = 0 + 1 + 2 + ... + n = n(n+1)/2 = O(n²).

Space Complexity: O(n)

The memo array uses O(n) space. The recursion stack can be at most O(n) deep (when the first recursive call always goes to cutRod(n-1)). Total space: O(n).

Why This Approach Is Not Efficient

Memoization solves the problem in O(n²) time and O(n) space, which is optimal in terms of asymptotic complexity for this problem. However, it has practical downsides:

1. Recursion overhead: Each subproblem incurs function-call overhead. For n = 1000, the recursion chain cutRod(1000) → cutRod(999) → ... → cutRod(1) creates a stack 1000 frames deep. While manageable in most environments, this adds constant-factor overhead and risks stack overflow for very deep chains.

2. Non-sequential memory access: The top-down approach fills the cache in the order determined by the recursion, not in a predictable sequential pattern. This can lead to more cache misses compared to iterative approaches that access memory in order.

3. Code complexity: The recursive structure with memoization requires managing the cache array and handling the base case check at every call. An iterative approach eliminates all of this.

The bottom-up tabulation approach achieves the same O(n²) time and O(n) space but iterates through subproblems in ascending order. This eliminates recursion entirely, provides better cache locality, and results in simpler, shorter code.

Optimal Approach - Bottom-Up Tabulation

Intuition

Instead of starting from the full rod and recursing downward, we flip the approach: start from the smallest rod (length 1) and build up to the full length.

Create a 1D array dp where dp[i] stores the maximum revenue for a rod of length i. We set dp[0] = 0 (base case) and fill the table from dp[1] to dp[n].

To compute dp[i], we try every possible first-cut length j from 1 to i. For each cut, the revenue is price[j] + dp[i - j]. Since i - j < i, dp[i - j] has already been computed in a previous iteration. We take the maximum over all cuts.

This is like a carpenter who first learns the best way to sell a 1-inch rod, then a 2-inch rod (using the 1-inch answer), then a 3-inch rod (using the 1-inch and 2-inch answers), and so on. By the time you reach the full length, every smaller subproblem is already solved.

The iterative approach avoids recursion entirely, accesses memory sequentially, and produces clean, readable code.

Step-by-Step Explanation

Let's trace with price = [2, 5, 7, 8] (rod length n = 4):

Initialize dp = [0, 0, 0, 0, 0]. dp[0] = 0 (no rod = no revenue).

Computing dp[1] (rod of length 1):

Step 1: j = 1: price[1] + dp[1-1] = 2 + dp[0] = 2 + 0 = 2. dp[1] = max(0, 2) = 2.

Computing dp[2] (rod of length 2):

Step 2: j = 1: price[1] + dp[2-1] = 2 + dp[1] = 2 + 2 = 4. Best so far: 4.

Step 3: j = 2: price[2] + dp[2-2] = 5 + dp[0] = 5 + 0 = 5. 5 > 4. dp[2] = 5. Selling as one length-2 piece is better.

Computing dp[3] (rod of length 3):

Step 4: j = 1: price[1] + dp[2] = 2 + 5 = 7. Best so far: 7.

Step 5: j = 2: price[2] + dp[1] = 5 + 2 = 7. Ties with best. Still 7.

Step 6: j = 3: price[3] + dp[0] = 7 + 0 = 7. All three options yield 7. dp[3] = 7.

Computing dp[4] (rod of length 4):

Step 7: j = 1: price[1] + dp[3] = 2 + 7 = 9. Best so far: 9.

Step 8: j = 2: price[2] + dp[2] = 5 + 5 = 10. 10 > 9. New best!

Step 9: j = 3: price[3] + dp[1] = 7 + 2 = 9. 9 < 10. No change.

Step 10: j = 4: price[4] + dp[0] = 8 + 0 = 8. 8 < 10. dp[4] = 10.

Final dp = [0, 2, 5, 7, 10]

Answer: dp[4] = 10. Two pieces of length 2 (5 + 5 = 10).

Bottom-Up Tabulation — Building Optimal Revenues Iteratively — Watch how the dp table fills from left to right. For each rod length, all possible first cuts are evaluated, using previously computed optimal values for the remaining piece.

Algorithm

  1. Create a 1D array dp of size n + 1, initialized to 0.
  2. For each rod length i from 1 to n:
    • For each first-cut length j from 1 to i:
      • Compute revenue = price[j] + dp[i - j]
      • Update dp[i] = max(dp[i], revenue)
  3. Return dp[n].

The key observation: when computing dp[i], all values dp[0] through dp[i-1] are already finalized. Since i - j < i for all valid j, every dependency is satisfied.

Code

#include <vector>
#include <algorithm>
using namespace std;

class Solution {
public:
    int cutRod(vector<int>& price) {
        int n = price.size();
        vector<int> dp(n + 1, 0);

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = max(dp[i], price[j - 1] + dp[i - j]);
            }
        }

        return dp[n];
    }
};
class Solution:
    def cutRod(self, price):
        n = len(price)
        dp = [0] * (n + 1)

        for i in range(1, n + 1):
            for j in range(1, i + 1):
                dp[i] = max(dp[i], price[j - 1] + dp[i - j])

        return dp[n]
class Solution {
    int cutRod(int[] price) {
        int n = price.length;
        int[] dp = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i] = Math.max(dp[i], price[j - 1] + dp[i - j]);
            }
        }

        return dp[n];
    }
}

Complexity Analysis

Time Complexity: O(n²)

The outer loop runs n times (for rod lengths 1 to n). For each length i, the inner loop runs i times (trying all cut positions). Total iterations: 1 + 2 + 3 + ... + n = n(n+1)/2 = O(n²). Each iteration does O(1) work.

Space Complexity: O(n)

We use a single 1D array dp of size n + 1. No recursion stack is needed. This is the minimum space required — we must store the optimal revenue for each rod length from 0 to n.

Compared to memoization, this approach has the same asymptotic complexity but eliminates recursion overhead, provides sequential memory access for better CPU cache performance, and uses shorter, simpler code.