Optimal Strategy for a Game using Dynamic Programming


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


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
  1. #include<iostream>
  2. using namespace std;
  4. int optimalGame(int n, int coins[])
  5. {
  6.     //matrix to store results
  7.     int dp[n][n];
  9.     //dp[i][j]=maximum amount you can definitely win if you move first with available coins[i...j]
  11.     int i,j;
  13.     //initialization
  14.     //if we have only one coin and we have to move first, we will pick that coin
  15.     for(j=0;j<n;j++)
  16.     {
  17.         dp[j][j]=coins[j];
  18.     }
  20.     //if we have only two coins and we have to move first, we will pick the coin of higher value
  21.     for(j=0;j<n-1;j++)
  22.         dp[j][j+1]=max(coins[j],coins[j+1]);
  24.     //we will calculate results for a row of i coins 
  25.     for(i=2;i<n;i++)
  26.     {
  27.         //we will calculate result dp[j][j+i]
  28.         for(j=0;j+i<n;j++)
  29.         {
  30.             int x=coins[j]+min(dp[j+2][j+i],dp[j+1][j+i-1]);
  31.             int y=coins[j+i]+min(dp[j+1][j+i-1],dp[j][j+i-2]);
  33.             dp[j][j+i]=max(x,y);
  34.         }
  35.     }
  37.     return dp[0][n-1];
  38. }
  40. int main()
  41. {
  42.     int i,n;
  43.     cout<<"Enter the number of coins"<<endl;
  44.     cin>>n;
  46.     int coins[n];
  48.     cout<<"Enter the values of coins"<<endl;
  49.     for(i=0;i<n;i++)
  50.         cin>>coins[i];
  52.     cout<<"The maximum amount of money we can definitely win, if we move first is "<<endl;
  53.     cout<<optimalGame(n,coins);
  55.     cout<<endl;
  56.     return 0;
  57. }
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
$ g++ optimal_game_strategy.cpp
$ ./a.out
Enter the number of coins
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 

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

Take Data Structure I Practice Tests - Chapterwise!
Start the Test Now: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10

Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.