Rod Cutting III
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 into at most maxPieces pieces (selling it whole is one piece) to maximize revenue, and return that revenue.
prices = [1, 5, 8, 9, 10, 17, 17, 20], n = 8 maxPieces = 1 -> 20 (sell it whole) maxPieces = 2 -> 22 (pieces 2 + 6)
prices has an entry for every length from 1 to n, and maxPieces is at least 1.
Hints
Hint 1
The one-dimensional table forgets how many pieces it used. Add that as a dimension: dp[k][L] is the best revenue for length L using at most k pieces.
Hint 2
dp[k][L] = max(dp[k-1][L], max over p of dp[k-1][L-p] + prices[p-1]). Unreachable states start at negative infinity, and dp[0][0] = 0.