Optimal Game Strategy: Maximum Coin Value

Maximum Coin Value

Consider a row of n coins of values (v1, ..., vn), where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.

Note: The opponent is as clever as the user.

Solution - Recursion

Translate the problem into mathematical language.
Let C(i, j) be coin values from i-th to j-th spot in the row and V[i] be the coin value at i-th spot.

• If we pick V[i], the opponent will take C[i+1] or V[j] so that the remaining give us minimal value, and then we continue on C(i+2, j) or C(i+1, j-1);
• If we pick V[j], the opponent will take V[i] or C[j-1] so that the remaining give us minimal value, and then we continue on C(i+1, j-1) or C(i, j-2).

Note that pick up the maximal (i.e. max(V[i], V[j])) in each round may not make you win with the overall maximum at the end. For example, given (10, 20, 8, 7), the maximum amount is 7+20=27.

So, the maximum amount of coins can be obtained from the following recursive formula:

maxCoin(i, j) = max(V[i] + min(maxCoin(i+2, j), maxCoin(i+1, j-1))
                                 V[j] + min(maxCoin(i+1, j-1), maxCoin(i, j-2)));
maxCoin(i, j) = V[i], if (i == j); maxCoin(i, j) = max(V[i], V[j]), if (i+1 == j).

It is easy to get a recursive function based on the above formula.
The running time of this algorithm is O(2^n) since we recalculate maxCoin for subarrays again and again.
Note: T(n) = O(1) + 4*T(n-2) = O(1) + 4*O(1) + 4*4*T(n-4) = ... = 1 + 4 + 4^2 + ... + 4^(n/2) = O(2^n).

Solution - DP

These repeat calculations give us a hint of using DP to store the intermediate results so as to reduce running time.

Suppose we have a 2-D table maxCoin[i, j] for max coin value of coins from i-th to j-th spot in the row. Now let's discuss how to fill up this table. As shown in the picture below, value of cell [i, j] can be calculated on three cells on the previous diagonal. So, we need to fill up the table diagonal by diagonal, from center diagonal to upper-right corner.

This algorithm runs in time O(n^2) and uses O(n^2) extra space.

 public int getMaxCoin(int[] coins) {  
   int n = coins.length;  
   int[][] maxCoin = new int[n][n];  
   
   // fill up the center diagomal  
   for (int i=0; i<n; ++i) {  
     maxCoin[i][i] = coins[i];  
   }  
   
   // fill up the table  
   for (int k=1; k<n; ++k) {  
     for (int i=0, j=k; i<n-k; ++i, ++j) {  
       int left = (i+2 <= j) ? maxCoin[i+2][j] : 0;  
       int bottom = (j-2 >= i) ? maxCoin[i][j-2] : 0;  
       maxCoin[i][j] = Math.max((coins[i] + Math.min(left, maxCoin[i+1][j-1])),  
                    (coins[j] + Math.min(maxCoin[i+1][j-1], bottom)));  
     }  
   }  
   
   return maxCoin[0][n-1];  
 }  

Note: This algorithm works for both cases where n is even or odd.

Solution - Another DP

Actually, since we assume that the opponent is as clever as ourselves, he will use the same strategy to pick up coins. That said,

• If we pick V[i], the money that opponent will get would be C(i+1, j);
• Similarly, if we pick V[j], the opponent would get C(i, j-1).

Now the goal is simply to select a coin such that the money that the opponent could achieve from the remaining coins is minimized.

Given coins from i-th to j-th, suppose we know the money of the opponent, how much can we get?
It will be the total value of all coins minus the coin values of the opponent!

The formula of the maximum coin value can be simplified as:

maxCoin(i, j) = max( Sum(i, j) - C(i+1, j), Sum(i, j) - C(i, j-1) );
maxCoin(i, j) = V[i], if (i == j); maxCoin(i, j) = max(V[i], V[j]), if (i+1 == j).

Unfortunately, The running time of this recursive algorithm is still O(2^n).
Note: T(n) = O(1) + 2*T(n-1) = O(1) + 2*O(1) + 2*2*T(n-2) = 1 + 2 + 4 + ... + 2^(n-1) = O(2^n).

But this formula can also lead to a DP solution.

Here we use one single n by n matrix for sum and maxCoin: the upper-right triangle for maxCoin and the bottom-left one for sum.

 public int getMaxCoin(int[] coins) {  
   int n = coins.length;  
   // For i<j, T[i][j] = maxCoin(i, j)  
   // For i>j, T[j][i] = sum(j, i)  
   int[][] T = new int[n][n];  
   
   for (int i=0; i<n; ++i) {  
     T[i][i] = coins[i];  
   }  
   
   for (int k=1; k<n; ++k) {  
     for (int i=0, j=k; i<n-k; ++i, ++j) {  
       // maxCoin(i, j) = max( Sum(i, j) - C(i+1, j), Sum(i, j) - C(i, j-1) );  
       T[j][i] = T[j-1][i] + coins[j];  
       T[i][j] = Math.max(T[j][i] - T[i+1][j], T[j][i] - T[i][j-1]);  
     }  
   }  
   
   return T[0][n-1];  
 }  

This algorithm has the same time and space complexity but the formula is simplified and no need to consider odd and even cases.