Full lesson preview

Find the maximum profit from rod cutting

Given prices for rod pieces, compute the maximum revenue obtainable by cutting a rod into integer lengths using dynamic programming.

Python practice15 minDynamic ProgrammingIntermediateLast updated March 29, 2026

Problem statement

You are given a list prices where prices[i] is the selling price of a rod piece of length i+1. Given an integer n (the length of the rod), determine the maximum revenue you can obtain by cutting the rod into integer-length pieces (including the option of not cutting it). Use dynamic programming to avoid redundant recomputation.

Task

Use bottom-up dynamic programming to compute the maximum revenue for a rod of length n given a price list for piece lengths.

Examples

Basic example

Input

rod_cut([1,5,8,9], 4)

Output

For a rod of length 4 with prices [1,5,8,9], cutting into two pieces of length 2 each (price 5 + 5) yields 10, which is maximum.

Input format

Function rod_cut(prices: list[int], n: int) -> int. prices[i] corresponds to price of piece length i+1.

Output format

Return an integer representing the maximum obtainable revenue.

Constraints

0 <= n <= 1000, 0 <= prices[i] <= 10^6. prices list may be shorter than n; missing prices should be treated as 0.

Samples

Sample 1

Input

rod_cut([2,5,7,3,9], 5)

Output

Best is to cut into lengths 2 and 3 (5 + 7 = 12).