Understanding solution to finding optimal strategy for game involving picking pots of gold

First of all a and b represent respectively the maximum gain if start (respectively end) is played.

So let explain this line:

int a = coin[start] + min(max_coin(coin, start+2, end), max_coin(coin, start+1, end-1))

If I play start, I will immediately gain coin[start]. The other player now has to play between start+1 and end. He plays to maximize his gain. However since the number of coin is fixed, this amounts to minimize mine. Note that

• if he plays start+1 I'll gain max_coin(coin, start+2, end)
• if he plays end Ill gain max_coin(coin, start+1, end-1)

Since he tries to minimize my gain, I'll gain the minimum of those two.

Same reasoning apply to the other line where I play end.

Note: This is a bad recursive implementation. First of all max_coin(coin, start+1, end-1) is computed twice. Even if you fix that, you'll end up computing lots of time shorter case. This is very similar to what happens if you try to compute Fibonacci numbers using recursion. It would be better to use memoization or dynamic programming.

a and b here represent the maximum A can get by picking the starting pot or the ending pot, respectively.

We're actually trying to maximize A-B, but since B = TotalGold - A, we're trying to maximize 2A - TotalGold, and since TotalGold is constant, we're trying to maximize 2A, which is the same as A, so we completely ignore the values of B's picks and just work with A.

The updated parameters in the recursive calls include B picking as well - so coin[start] represents A picking the start, then B picks the next one from the start, so it's start+2. For the next call, B picks from the end, so it's start+1 and end-1. Similarly for the rest.

We're taking the min, because B will try to maximize it's own profit, so it will pick the choice that minimizes A's profit.

But actually I'd say this solution is lacking a bit in the sense that it just returns a single value, not 'an optimal strategy', which, in my mind, would be a sequence of moves. And it also doesn't take into account the possibility that A can't win, in which case one might want to output a message saying that it's not possible, but this would really be something to clarify with the interviewer.

Let me answer your points in reverse order, somehow it seems to make more sense that way.

3 - a and b represent the amount of coins the first player will get, when he/she chooses the first or the last pot respectively

2 - we take the minimum because it is the choice of the second player - he/she will act to minimise the amount of coins the first player will get

1 - the first line presents the scenario - if the first player has taken the first pot, what will the second player do? If he/she again takes the first pot, it will leave (start+2, end). If he/she takes the last pot, it will leave (start+1, end-1)