Rod Cutting
Let's solve the Rod Cutting problem using Dynamic Programming.
Statement
You are given a rod of length n
meters. You can cut the rod into smaller pieces, and each piece has a price based on its length. Your task is to earn the maximum revenue that can be obtained by cutting up the rod into smaller pieces.
Let’s say you have a rod of length meters and you have two lists: one that defines the lengths, and the other that defines the price of each length.
lengths = [1, 3, 4]
prices = [2, 7, 8]
You can cut the rod into the pieces of varying lengths and earn the following revenues:
-
Four pieces of length meter
-
One piece of length meter and another piece of length meters
-
One single piece of length meters
Therefore, the maximum revenue you can generate by cutting the rod and selling the pieces is , by cutting the rod into two pieces, one of length and the other of length .
Constraints:
-
n
-
prices[i]
-
lengths[i]
prices.length
lengths.length
Examples
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.