Optimal Game Strategy Problem

This is a C++ Program that Solves Optimal Game Strategy Problem using Dynamic Programming technique.

Problem Description

This is a two player game. There are even number of coins arranged in a row. There will be alternate turns. In each turn, a player can either select the first coin in the row or the last coin in the row and keep it with him. The objective of the problem is to determine the maximum possible amount of money a player can definitely win, if he move first.

Problem Solution

In this problem, we will try to collect maximum amount without underestimating the opponent. We can choose either the first or the last coin in the row. We will pick the one which results in giving us lesser amound to ensure that we can definitely win this much of amount irrespective of opponent’s moves.

Expected Input and Output

Case-1:

 
coins[]=4, 15, 7, 3, 8, 9
Expected result=27

Program/Source Code

Here is source code of the C++ Program to Solve Optimal Game Strategy Problem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

Note: Join free Sanfoundry classes at Telegram or Youtube

```
#include<iostream>
```
```
using namespace std;
```
```
 
```
```
int optimalGame(int n, int coins[])
```
```
{
```
```
    //matrix to store results
```
```
    int dp[n][n];
```
```
 
```

    //dp[i][j]=maximum amount you can definitely win if you move first with available coins[i...j]

```
 
```
```
    int i,j;
```
```
 
```
```
    //initialization
```

    //if we have only one coin and we have to move first, we will pick that coin

```
    for(j=0;j<n;j++)
```
```
    {
```
```
        dp[j][j]=coins[j];
```
```
    }
```
```
 
```

    //if we have only two coins and we have to move first, we will pick the coin of higher value

```
    for(j=0;j<n-1;j++)
```

        dp[j][j+1]=max(coins[j],coins[j+1]);

```
 
```

    //we will calculate results for a row of i coins

```
    for(i=2;i<n;i++)
```
```
    {
```

        //we will calculate result dp[j][j+i]

```
        for(j=0;j+i<n;j++)
```
```
        {
```

            int x=coins[j]+min(dp[j+2][j+i],dp[j+1][j+i-1]);

            int y=coins[j+i]+min(dp[j+1][j+i-1],dp[j][j+i-2]);

```
 
```
```
            dp[j][j+i]=max(x,y);
```
```
        }
```
```
    }
```
```
 
```
```
    return dp[0][n-1];
```
```
}
```
```
 
```
```
int main()
```
```
{
```
```
    int i,n;
```

    cout<<"Enter the number of coins"<<endl;

```
    cin>>n;
```
```
 
```
```
    int coins[n];
```
```
 
```

    cout<<"Enter the values of coins"<<endl;

```
    for(i=0;i<n;i++)
```
```
        cin>>coins[i];
```
```
 
```

    cout<<"The maximum amount of money we can definitely win, if we move first is "<<endl;

```
    cout<<optimalGame(n,coins);
```
```
 
```
```
    cout<<endl;
```
```
    return 0;
```
```
}
```

Program Explanation

In the main function, we ask the user to input the value for number of coins and the value of each coin. We pass this value to the function optimalGame as parameter. This function will calculate the expected result and return it. The returned value will be displayed.

Runtime Test Cases

 
Case-1:
$ g++ optimal_game_strategy.cpp
$ ./a.out
Enter the number of coins
6
Enter the values of coins
4 15 7 3 8 9
The maximum amount of money we can definitely win, if we move first is 
27

Sanfoundry Global Education & Learning Series – Dynamic Programming Problems.
To practice all Dynamic Programming Problems, here is complete set of 100+ Problems and Solutions.