Rod Cutting I
You have a rod of length n and a price table: prices[i] is what a piece of length i + 1 sells for. Cut the rod (or don't) to maximize revenue, and report the cuts: return [revenue, pieceLengths].
prices = [1, 5, 8, 9, 10, 17, 17, 20], n = 8 -> [22, [2, 6]] (pieces 2 + 6: 5 + 17)
The price table may be shorter than n: lengths beyond it can't be sold, so those pieces must be cut smaller. Any cut list that sums to n and earns the maximum is accepted.
Hints
Hint 1
best[L] = max over first-piece lengths p of prices[p-1] + best[L-p]. One dimension, filled left to right — this is unbounded knapsack with weight = length, value = price.
Hint 2
To recover the cuts, store the winning first-piece length per L and walk it back.