[Java] Maximise alternate picks on array - dynamic programming

Last time we saw how to find the maximum achievable value in a situation where two players alternate in picking items from an array boundaries. Solution works, but runs in O(2^N) which becomes quickly unacceptable.

If we introduce a bit more complexity, we can take that time and space down to O(N^2), which is still not awesome but definitely better than before. The key is to track calculations that have already been done to reuse those values later on; this translates in us keeping a matrix of size 2xN^2 where for each player we track the best pick at a specific point in time. When we get to evaluate that pick again, if the result is already cached, we can simply return it and avoid extra function calls.

This performance change can be easily tracked by keeping a global counter starting at 0 and increasing it by 1 at the beginning of the helper function. At the end of the algorithm we will see the total number of functions calls for both methods.

You can check my implementation of getMaxGoldFromPots on my Gist alongside some test cases in GoldPotsJTests.

Note: The test cases are exactly the same, therefore to try either approach simply rename the function calls in the JUnit tests.