This is a C++ Program that Solves Optimal Game Strategy Problem using Dynamic Programming technique.
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.
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.
coins=4, 15, 7, 3, 8, 9 Expected result=27
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.
using namespace std;
int optimalGame(int n, int coins)
//matrix to store results
//dp[i][j]=maximum amount you can definitely win if you move first with available coins[i...j]
//if we have only one coin and we have to move first, we will pick that coin
//if we have only two coins and we have to move first, we will pick the coin of higher value
//we will calculate results for a row of i coins
//we will calculate result dp[j][j+i]
cout<<"Enter the number of coins"<<endl;
cout<<"Enter the values of coins"<<endl;
cout<<"The maximum amount of money we can definitely win, if we move first is "<<endl;
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.
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.