Optimal Strategy for a Game

Following is the recursive solution that is based on the above two choices. We take a maximum of two choices. 

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) ))
As user wants to maximise the number of coins. 

Base Cases
    F(i, j) = Vi           If j == i
    F(i, j) = max(Vi, Vj)  If j == i + 1
    
    Gap strategy
    long long maximumAmount(int arr[], int n) 
{
    int dp[n][n];
    
    for(int g=0;g<n;g++){
        for(int i=0,j=g;j<n;i++,j++){
            
            if(g==0)
                dp[i][j]=arr[i];
                
            if(g==1)
                dp[i][j]=max(arr[i],arr[j]);
                
            else{
                int q1=arr[i]+min(dp[i+2][j],dp[i+1][j-1]);
                int q2=arr[j]+min(dp[i][j-2],dp[i+1][j-1]);
                int val=max(q1,q2);
                dp[i][j]=val;
            }
        }
    }
     return dp[0][n-1];   
        
    
    // Your code here
}