Rod Cutting

Given a nonempty price array of length n, price[i] is the selling price of a piece of length i+1. Cut a rod of length n into positive integer-length pieces to…

Given a nonempty price array of length n, price[i] is the selling price of a piece of length i+1. Cut a rod of length n into positive integer-length pieces to maximize the total selling price. You may repeat piece lengths, must use the entire rod, and may leave it uncut. Return the maximum total price.

- 1 <= n = price.length <= 1000. - Each price is an integer from 1 through 100000. - The visualizer accepts n <= 8; larger valid inputs are coding-only.

Example 1: input price = [1,5,8,9]; output 10. Two length-2 pieces sell for 5+5=10, beating the uncut price 9.

Example 2: input price = [1,2,10]; output 10. The uncut length-3 rod sells for 10; every cut sells for less.

Example 3: input price = [4,5,6]; output 12. Three length-1 pieces sell for 12.

Category: Arrays. Topic: dynamic-programming. Difficulty: hard. Patterns: dynamic-programming.