GeeksforGeeks Medium

Rod Cutting Problem

A rod of length n can be cut into integer pieces, where a piece of length i sells for price[i-1]. Maximise the total selling value.

dpknapsack

Open on GeeksforGeeks ↗

02

Intuition

💡

This is knapsack with unlimited copies: piece lengths can be reused as often as they fit. The trick that collapses the search is to fix only the first piece. Whatever the optimal cutting looks like, it starts with some piece of length f; the rest of the rod is then an independent, already-solved subproblem of length n − f. Trying every f and trusting dp for the remainder covers every possible cutting without ever enumerating them.

03

Approach

1

One dimension is enough

dp[L] = best value obtainable from a rod of length L. dp[0] = 0, since a rod of nothing sells for nothing.

2

Fix the first cut only

dp[L] = max over f in 1..L of price[f-1] + dp[L - f]. The recursion never needs to know which pieces came before.

3

Sweep upward for reuse

Unlike 0/1 knapsack, dp[L - f] may already include piece f. That is correct here — pieces are unlimited, so the upward sweep is the feature, not a bug.

04

Solution & live demo

python

▶1class Solution:
▶2    def cutRod(self, price):
▶3        n = len(price)
▶4        dp = [0] * (n + 1)
▶5        for length in range(1, n + 1):
▶6            best = 0
▶7            for first in range(1, length + 1):
▶8                # sell one piece of 'first', reuse the solved remainder
▶9                best = max(best, price[first - 1] + dp[length - first])
▶10            dp[length] = best
▶11        return dp[n]

05

Edge cases

n = 0

dp[0] = 0; the loop body never executes.

Selling whole beats cutting

f = L is one of the candidates, so the uncut rod is always considered.

Price list shorter than n

Not applicable — price is indexed 1..n by definition, so every length has a price.

06

Complexity

Time

O(n²)

Space

O(n)

Each of n lengths tries up to n first-cuts. The naive recursion is O(2ⁿ) because it re-solves the same remainders.