Rod Cutting

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

Input / Output

• Input: int n, int array price (1-indexed by length).
• Output: maximum revenue.

Constraints

• n up to a few thousand — O(n^2) DP intended.

Example

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

Expected approach

• Unbounded-knapsack DP: dp[0] = 0; dp[i] = max over j in [1..i] of price[j] + dp[i−j]. O(n^2) time, O(n) space. Reconstruct the cut list by remembering the argmax j per i — a standard follow-on. Variants asked as "variations": limited piece counts (bounded knapsack), cost per cut (subtract per cut), or specific piece lengths only — say how each perturbs the recurrence.