Rod Cutting Problem
Build a recursive solution for a commonly asked coding interview problem.
We'll cover the following
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.