Challenge: The Rod Cutting Problem

Problem statement

You are given a rod of length n meters. You want to sell the rod and earn revenue. You can cut the rod into multiple smaller pieces of sizes $1$ through $n$ and sell them too. You are given the price of each size of the rod. Since you want to earn more, you will have to look for the optimal cuts on the rod that would earn the most revenue.

Input

Your function would get as input n, the original length of the rod. You can cut the rod into different pieces of sizes $1,2,$ up to $n$. The price for each of these pieces is given in a list of size $n$ called prices.

n = 4
prices = [2,3,7,8]

Output

Your function should return the optimal amount of revenue you can get out of the rod provided n and prices.

n = 4
prices = [2,3,7,8]
rodCutting(n, prices) = 9

Coding challenge

You may write either a bottom-up or a top-down dynamic programming algorithm. If you plan to write a recursive algorithm first, you may check its correctness by setting the stressTesting variable to False.

Think carefully about the problem. Think about strategies to memoize or tabularize the problem, and then write the code. Best of luck!