Rod Cutting

Medium20–25 min

Topics

Dynamic ProgrammingArray

Companies

AmazonMicrosoftDirecti

A rod of a certain length can be sold whole or cut into smaller pieces, each length having its own fixed selling price. Given the price for every possible piece length from 1 up to the rod's full length, decide how to cut the rod — into any number of pieces of any lengths, each used as often as needed — to maximize the total revenue from selling all the pieces. Every rod length boils down to a choice of where to make the first cut: sell the piece cut off at that length for its listed price, then face the exact same decision on whatever length remains. Trying every possible first-cut length and combining its price with the best revenue already known for the leftover length finds the best total for that starting length. Because shorter lengths are solved before longer ones ever need them, building the answer up from length 0 to the full rod length turns an exponential search into a simple sweep.

Test Case 1:

Input:prices = [3, 6, 4, 9, 2]

Output:15

Explanation:Cutting the length-5 rod into five length-1 pieces gives 5 × 3 = 15, which beats every other combination of cuts.

Test Case 2:

Input:prices = [5, 8]

Output:10

Explanation:Cutting the length-2 rod into two length-1 pieces gives 2 × 5 = 10, beating the single length-2 piece worth 8.

Test Case 3:

Input:prices = [6, 4, 10, 3, 12]

Output:30

Explanation:Cutting the length-5 rod into five length-1 pieces gives 5 × 6 = 30, beating every other combination of cuts.

Constraints

◆1 ≤ prices.length ≤ 20
◆0 ≤ prices[i] ≤ 1000

🚀

Try the Dry Run

Don't just read the solution — watch it execute, one step at a time.

Approach & Solutions

Brute Force — Recursive Without Memoization

Brute

A rod of a given length can be sold whole, or cut into a first piece of any length from 1 up to the rod's own length, sold at that piece's price, with the rest of the rod — now shorter — facing the exact same decision all over again. Since it's not obvious in advance which first cut leads to the best total revenue, every possible first-cut length is tried, each paired with the best revenue achievable from whatever length remains afterward, and the largest total across every choice is kept. A rod of length 0 contributes nothing and ends the recursion.

TimeO(2^n)

SpaceO(n)

Java

Try it out

class Solution {
    private int[] prices;

    public int rodCutting(int[] prices) {
        this.prices = prices;
        return solve(prices.length);
    }

    private int solve(int len) {
        if (len == 0) return 0;
        int best = 0;
        for (int L = 1; L <= len; L++) {
            best = Math.max(best, prices[L - 1] + solve(len - L));
        }
        return best;
    }
}

Optimal — Bottom-Up 1D DP

Optimal

Track, for every rod length from 0 up to the full length, the best revenue achievable by cutting it up. A length-0 rod is worth nothing, and every later length's best revenue comes from trying every possible first-cut length up to it and adding that piece's price to the best revenue already worked out for whatever length remains — since shorter lengths are always filled in before a longer one needs them, that smaller answer is already sitting in the table. The largest total across every first-cut choice becomes that length's entry, and the entry at the full rod length holds the final answer.

TimeO(n²)