[Java] Maximise profit to cut rod

Given a rod of length N and an array indicating the profit from selling a rod of length i + 1, find the best way to cut up the rod in order to maximise the profit of selling all the pieces. Not cutting the rod at all is also a valid option.

Example:

[1,5,2,7]

means our profit for selling a rod piece of length 1 is 1, length 2 is 5, etc

If we picked length 4, the best would be cutting it in two pieces of length 2 for a total profit of 10.

We can use a DFS recursive approach where for each rod size from 1 to N and all possible cuts of a rod of that size, we pick the best between profit of NOT cutting rod and profit of cutting on that length + best profit of cutting the remainder.

Since we have two possible choices at each step, our algorithm runs in O(2 ^N) time and uses O(N) space as at most our DFS depth will reach the length of the rod.

We can improve this in two ways using dynamic programming:

(1) caching results while doing the same DFS recursive approach

We use an additional array of length rodSize + 1 and initialize it to all -1 values.

During our recursion, we check if we already have a cached value for the best profit of cutting a rod of size S, if yes we return it, otherwise we calculate it and then cache it.

(2) building up our knowledge of the best cut combinations from the ground up

We use an additional array of length rodSize + 1 and initialize cell 0 to value 0. This represents the fact that a rod of length 0 yields 0 profit.

Then we expand from a rod of size 1 to size N inclusive each time to calculating the max profit between all possible cuts of a rod of that length.

At each step the max profit for length L and cut C is profit[C] + profit[L-C].

In both cases we evaluate all cuts from 1..length for each length in 1..N, which is a O(N^2) algorithm. This is easier to notice in approach (2).

In terms of space we use the additional O(N) space for the cache.

If we also wanted to know which cuts produce that profit, we need to create an additional array of length rodSize + 1 and we would store there the cut length C that produced the max profit for the rod of length L.

At the end, we have the length of the initial cut in position rodSize of this array. The previous cut to contribute to that best value if found in position array[rodSize - array[rodSize]] that is, the length resulting from cutting the rod by the length of the cut that produced the best result for the current length.

We can continue to backtrack as long as we reach the length 0.

You can check my implementation of maxRodCutProfit (recursive non optimized approach), maxRodCutProfitDP (memoized recursive approach) and maxRodCutProfitDPBottomUp (iterative optimized approach) on my Gist along with some tests in MaxRodCutProfitJTests.