Dynamic Programming | Set 31 (Optimal Strategy for a Game) | GeeksforGeeks

Dynamic Programming | Set 31 (Optimal Strategy for a Game) | GeeksforGeeks

Problem statement: 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.

F(i, j)  represents the maximum value the user can collect from 
         i'th coin to j'th coin.

    F(i, j)  = Max(Vi + min(F(i+2, j), F(i+1, j-1) ), 
                   Vj + min(F(i+1, j-1), F(i, j-2) )) 
Base Cases
    F(i, j)  = Vi           If j == i
    F(i, j)  = max(Vi, Vj)  If j == i+1

// Returns optimal value possible that a player can collect from

// an array of coins of size n. Note than n must be even

int optimalStrategyOfGame(int* arr, int n)

{

    // Create a table to store solutions of subproblems

    int table[n][n], gap, i, j, x, y, z;

    // Fill table using above recursive formula. Note that the table

    // is filled in diagonal fashion (similar to http://goo.gl/PQqoS),

    // from diagonal elements to table[0][n-1] which is the result.

    for (gap = 0; gap < n; ++gap)

    {

        for (i = 0, j = gap; j < n; ++i, ++j)

        {

            // Here x is value of F(i+2, j), y is F(i+1, j-1) and

            // z is F(i, j-2) in above recursive formula

            x = ((i+2) <= j) ? table[i+2][j] : 0;

            y = ((i+1) <= (j-1)) ? table[i+1][j-1] : 0;

            z = (i <= (j-2))? table[i][j-2]: 0;

            table[i][j] = max(arr[i] + min(x, y), arr[j] + min(y, z));

        }

    }

    return table[0][n-1];

}

http://n00tc0d3r.blogspot.com/2013/07/optimal-game-strategy-maximum-coin-value.html
Solution - Another DP
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).

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];  
 }

Read full article from Dynamic Programming | Set 31 (Optimal Strategy for a Game) | GeeksforGeeks