Proficient Level
Implement the rodCuttingMaximumProfit method that finds the maximum profit obtainable by cutting a rod into pieces.
The input contains an array prices, its length size, and the rod length n. The value at prices[i - 1] represents the selling price of a rod piece of length i.
Your task is to cut the rod into one or more pieces, or leave it uncut, so that the total selling price is maximum. For example, for rod length 8 and prices [1,5,8,9,10,17,17,20], the maximum profit is 22.
Example 1
Input
prices (int[]) =
[1,5,8,9,10,17,17,20]size (int) =
8n (int) =
8Returns (int)
22Example 2
Input
prices (int[]) =
[2,5,7]size (int) =
3n (int) =
3Returns (int)
7Example 3
Input
prices (int[]) =
[3]size (int) =
1n (int) =
1Returns (int)
3This is an unbounded dynamic programming problem because the same piece length can be used multiple times.
Let dp[length] store the maximum profit for a rod of that length. For every length, try all possible first cuts. If the first cut has length cut, the profit is prices[cut - 1] + dp[length - cut].
Choose the maximum value among all possible cuts.
Pseudocode:
function rodCuttingMaximumProfit(prices, size, n):
dp = array of n + 1 values filled with 0
for lengthValue from 1 to n:
best = 0
for cut from 1 to lengthValue:
if cut <= size:
best = max(best, prices[cut - 1] + dp[lengthValue - cut])
dp[lengthValue] = best
return dp[n]Ready to test your solutionRun Code checks your solution against the test cases.Shift + Enter to run