Rod Cutting II
You have a rod of length n and a price table: prices[i] is what a piece of length i + 1 sells for. Every cut costs cutCost; selling the rod whole makes zero cuts, and k pieces take k − 1 cuts. Return the maximum net profit: total price of the pieces minus the cost of the cuts.
prices = [1, 5, 8, 9, 10, 17, 17, 20], n = 8 cutCost = 0 -> 22 (pieces 2 + 6, one free cut) cutCost = 1 -> 21 (the same cut, now costing 1) cutCost = 100 -> 20 (sell it whole)
prices has an entry for every length from 1 to n.
Hints
Hint 1
Seed best[L] with selling length L whole — zero cuts. Then every split into a first piece plus the rest adds exactly one cut.
Hint 2
best[L] = max(prices[L-1], max over p < L of prices[p-1] − cutCost + best[L-p]). The best[L-p] term already paid for its own cuts.