Search⌘ K
AI Features
Home
Courses
Dynamic Programming in Python: Optimizing Programs for Efficiency

Challenge: The Rod Cutting Problem

Learn how to approach the rod cutting problem by applying dynamic programming methods. Understand how to optimize revenue by deciding the best way to cut a rod into smaller pieces based on given prices. Practice implementing both top-down and bottom-up strategies to enhance your problem-solving skills in algorithm optimization.

We'll cover the following...

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 11 through nn 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,1,2, up to nn. The price for each of these pieces is given in a list of size nn 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!

Python 3.5
def rodCutting(n, prices):
  # write your code here
  return 0
stressTesting = True

In the next lesson, we will review some solutions to this problem.