Rod Cutting Problem

Build a recursive solution for a commonly asked coding interview problem.

Problem statement

You are given a rod of size n > 1, it can be cut into any number of pieces k. The price for each piece of size i is represented as price(i) and the maximum revenue from a rod of size i is r(i) (could be split into multiple pieces). Find r(n) for the rod of size n.

Consider that the length of the rod is 6. The price of size is given below:

Length 1 2 3 4 5 6
Price(p) 2 5 8 9 10 11

The possible number of rods after cutting can give the following price:

Rod(6) 1*6 1*4, 2 1*3, 3 1, 2, 3 1*2, 4 1, 5 2*3 2, 4 3, 3
Price(p) 12 13 14 15 13 12 15 13 16

So the maximum revenue is 16 for the rod that can be cut in (3,3), i.e., 2 pieces.

Solution: Recursive Approach

Here we have to generate all the configurations of different pieces and find the highest priced configuration. We can get the best price (maximum revenue) by making a cut at different positions and comparing the values obtained after a cut.

If RodCut(n) is the function that gives the value of r(n), then RodCut(n) = max(p(i) + RodCut(i)).

Let’s move to the implementation now. In this lesson, we will build a solution using the recursive approach, and then in the next lesson, we will implement a more optimized approach to solve this problem.

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.