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 $4$ 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 $1$ meter $= 2 + 2 + 2 + 2 = 8$

One piece of length $1$ meter and another piece of length $3$ meters $= 2 + 7 = 9$

One single piece of length $4$ meters $= 8$
Therefore, the maximum revenue you can generate by cutting the rod and selling the pieces is $9$, by cutting the rod into two pieces, one of length $1$ and the other of length $3$.
Constraints:
 $1\leq$
n
$\leq40000$  $1\leq$
prices[i]
$\leq10^6$  $1\leq$
lengths[i]
$\leq n$ prices.length
$=$lengths.length
Examples
Level up your interview prep. Join Educative to access 80+ handson prep courses.