Rod Cutting Problem

Q: What is the time complexity of the rod cutting problem?

The table takes O(n²) time and O(n) memory: length len tries len first pieces, n(n+1)/2 tries in all. Without stored answers the recursion makes exactly 2^n calls for a rod of length n, since each length calls every shorter length.

Q: Why is rod cutting an unbounded knapsack problem?

Treat each piece length k as an item of weight k and value prices[k-1] , with unlimited copies, and the rod as a bag of capacity n that must be filled exactly. The best total value of the items is then the best price for the rod.

Q: How do you find where to cut the rod?

Store, for each length, the first piece k that gave its best price. Start at length n: cut a piece of the stored length, move to the length that is left, and repeat until it reaches 0. The pieces form one best plan.

MediumDynamic programming

+10

You have a rod of length n, where n = prices.length. A piece of length k sells for prices[k-1]. You may cut the rod into pieces of whole lengths, as many as you like, or sell it in one piece. Return the most money you can earn by selling all of it.

Function

cutRod(prices: integer-array) → integer

pricesinteger-array: prices[k-1] is the price of a piece of length k; the rod is prices.length long
Returnsinteger: the most money the whole rod can earn

Constraints

1 ≤ prices.length ≤ 1000
1 ≤ prices[i] ≤ 10⁵

Examples

Input: prices = [2, 5, 7, 8]
Output: 10
Explanation: Two pieces of length 2 sell for 5 + 5 = 10. Selling the rod whole earns 8, and a piece of 1 plus a piece of 3 earns 2 + 7 = 9.

Follow-up

What if you may cut the rod at most m times? What does each table entry need to know then?

Hints

Open them one at a time. Each one gives away a little more.

0 of 3 opened

Solution

A rod of length n has 2^(n-1) ways to be cut. You never need them all: whatever the first piece is, the rest is a shorter rod asking the same question. So only n+1 answers exist, one per length, and working them out from the shortest up takes O(n²) steps.

Try every length for the first piece

Correct, but does not finish on the largest tests

Intuition

Whatever the plan, the piece at the left end has some length k from 1 to the rod's length and earns prices[k-1]; the rest of the plan cuts a rod of length length-k. So best(length) is 0 for length 0, and otherwise the largest prices[k-1] + best(length-k) over all k, where k = length sells the rod whole. Every plan has a first piece, so this maximum covers every plan.

Each call branches into every shorter length, so the number of calls doubles with each unit of length: a rod of 40 makes about 2^40, or 10^12, calls.

Algorithm

Write best(length), which returns 0 for length 0.
For each first piece k from 1 to length, compute prices[k-1] + best(length-k).
Return the largest of those values.
Return best(n).

def cutRod(prices):
    # The most money a rod of this length can earn
    def best(length):
        top = 0
        for piece in range(1, length + 1):
            # sell a first piece of this length, then cut the rest as well as possible
            top = max(top, prices[piece - 1] + best(length - piece))
        return top

    return best(len(prices))

Best price for every length, shortest first

Intuition

The recursion recomputes the same values: best(2) is asked for by best(3), best(4) and every longer rod. There are only n+1 lengths, so compute each once into an array best. A length reads only shorter lengths, so filling the array from 0 upward means every value is ready when it is read.

On [2, 5, 7, 8]: best[1] is 2, best[2] is the larger of 2 + 2 and 5, so 5, best[3] is 7, and best[4] is the largest of 2 + 7, 5 + 5, 7 + 2 and 8, so 10.

Unlike the 0/1 knapsack, best[len-k] may already contain pieces of length k, and that is what you want, since a length can be cut as often as you like. Length len tries len first pieces: n(n+1)/2 steps in all, about 5 × 10^5 for a rod of 1000.

Algorithm

Make best with n + 1 entries, all 0.
For each length from 1 to n, try every first piece k from 1 to length.
Compute prices[k-1] + best[length-k] and keep the largest in best[length].
Return best[n].

def cutRod(prices):
    n = len(prices)
    # best[length]: the most money a rod of that length can earn
    best = [0] * (n + 1)
    for length in range(1, n + 1):
        for piece in range(1, length + 1):
            # a first piece of this length, then the best for what is left
            earned = prices[piece - 1] + best[length - piece]
            if earned > best[length]:
                best[length] = earned
    return best[n]

Pitfalls and edge cases

Reading prices[k] for length k. That prices every piece one size too long and runs past the end at k = n; use prices[k-1].
Leaving out k = length, the uncut piece. Then best[1] stays 0, and [1, 3, 8] scores 3 instead of 8.
Cutting greedily by the best price per unit. On [2, 7, 11, 13], length 3 earns the most per unit, but 11 for it plus 2 for the leftover makes 13, while two pieces of length 2 make 14.
Memoizing top-down in Python. The recursion still nests as deep as the rod is long: a rod of 1000 nests 1001 calls, past the default limit of 1000. Fill the array bottom up.

Frequently asked questions4

What is the time complexity of the rod cutting problem?

The table takes O(n²) time and O(n) memory: length len tries len first pieces, n(n+1)/2 tries in all. Without stored answers the recursion makes exactly 2^n calls for a rod of length n, since each length calls every shorter length.

Why is rod cutting an unbounded knapsack problem?

Treat each piece length k as an item of weight k and value prices[k-1], with unlimited copies, and the rod as a bag of capacity n that must be filled exactly. The best total value of the items is then the best price for the rod.

How do you find where to cut the rod?

Store, for each length, the first piece k that gave its best price. Start at length n: cut a piece of the stored length, move to the length that is left, and repeat until it reaches 0. The pieces form one best plan.

How does the solution change if every cut costs money?

Selling the rod whole involves no cut, while every other first piece adds one cut. So best[len] becomes the larger of prices[len-1] and the largest prices[k-1] + best[len-k] - cost for k below len. The rest of the table stays the same.

def cutRod(prices):
    # Write code here

Test #1

Test #2

Test #3

Argument

prices = [2, 5, 7, 8]

Expected Output