Rod Cutting

Problem Given a rod of length n and a price table where price[j] is the value of a piece of length j, cut the rod into pieces (any number of cuts, including none) to maximize total revenue.

Input / Output

• Input: integer n, and array price 1-indexed by piece length.
• Output: the maximum revenue obtainable.

Constraints

• n up to a few thousand — an O(n^2) DP is the intended complexity.
• Pieces may be any length in 1..n, and a length may be used any number of times.

Example

• n = 8, price = [1,5,8,9,10,17,17,20] -> 22 (cut into 2 + 6, giving 5 + 17).