Rod Cutting
Intermediate
A rod has integer length length. prices[i] is the price of a piece of length i + 1. You may cut the rod into pieces of integer lengths (or not cut at all). Return the largest total price. The length is at most len(prices).
For prices = [1, 5, 8, 9, 10, 17, 17, 20] and length = 8 the answer is 22 (pieces of length 2 and 6).
Examples
Example 1
Input:
rod_cutting([1, 5, 8, 9, 10, 17, 17, 20], 8)
Output:
22
Example 2
Input:
rod_cutting([3, 5, 8, 9, 10, 17, 17, 20], 8)
Output:
24
Constraints
0 <= length <= len(prices) <= 20000 <= prices[i] <= 10000
Theory
Go to TheoryKeywords
dsa-sheetdynamic-programmingknapsack
Run your code to see results
No results yet
Run your code to check it against the examples, or submit to run every test.