This post is completed by 3 users

  • 1
Add to List
Medium

170. Dynamic Programming - Rod Cutting Problem

Objective: Given a rod of length n inches and a table of prices pi, i=1,2,…,n, write an algorithm to find the maximum revenue rn obtainable by cutting up the rod and selling the pieces.

This is a very good basic problem after Fibonacci sequence if you are new to Dynamic programming. We will see how dynamic programming is used to overcome the issues with recursion(Time Complexity).

Given: Rod lengths are integers and For i=1,2,…,n we know the price pi of a rod of length i inches

Example:

Length 1 2 3 4 5 6 7 8 9 10
Price 1 5 8 9 10 17 17 20 24 30
for rod of length: 4
Ways to sell :
•	selling length : 4  ( no cuts) , Price: 9
•	selling length : 1,1,1,1  ( 3 cuts) , Price: 4
•	selling length : 1,1,2  ( 2 cuts) , Price: 7
•	selling length : 2,2  ( 1 cut) , Price: 10
•	selling length : 3, 1  ( 1 cut) , Price: 9

Best Price for the rod of length 4: 10

Approach:

Naive Approach: Recursion

  • There can be n-1 cuts can be made in the rod of length n, so there are 2n-1 ways to cut the rod.
  • So for every length, we have 2 options either we cut it or not. we will consider both options and choose the optimal out of it.

Time Complexity: O(2^n-1)
But this time complexity is very high since we are solving many subproblems repeatedly.

Rod Cutting Problem - Overlapping Sub problems
Rod Cutting Problem - Overlapping Subproblems

Dynamic Programming: Bottom-Up

Instead of solving the sub-problems repeatedly we can store the results of it in an array and use it further rather than solving them again.

See the Code for a better explanation:

Result: Max profit for length is 5:11
Rod Cutting Problem - Solution Matrix