Rod cutting for maximum revenue

Question

You have a rod of integer length n and a price list where price[k] is what a piece of length k sells for. You may cut the rod into any number of integer-length pieces (or leave it whole). Return the maximum total revenue. Return the best revenue. Target O(n^2).

Accepted Answer

This is the coin-change skeleton with two changes: we maximize a value instead of minimizing a count, and each "coin" is a cut of length c that adds price[c]. Let dp[L] be the best revenue for a rod of length L, with dp[0] = 0. For each L, try making a first cut of every length c from 1 to L, earn price[c], and then optimally cut the remaining L - c: dp[L] = \max{1 \le c \le L} \big( price[c] + dp[L - c] \big). Tracing price = [0, 1, 5, 8, 9], n = 4: dp[1] = 1, dp[2] = max(1 + dp[1], 5 + dp[0]) = 5, dp[3] = max(1 + dp[2], 5 + dp[1], 8 + dp[0]) = 8, and dp[4] = max(1 + dp[3], 5 + dp[2], 8 + dp…

Rod cutting for maximum revenue

Your answer

More Coding questions