Find the winner of a game of removing at most 3 stones from a pile in each turn | C ++ program for the above approach ; Function to find the maximum score of Player 1 ; Base Case ; If the result is already computed , then return the result ; Variable to store maximum score ; Pick one stone ; Pick 2 stones ; Pick 3 stones ; Return the score of the player ; Function to find the winner of the game ; Create a 1D table , dp of size N ; Store the result ; Player 1 wins ; PLayer 2 wins ; Tie ; Driver Code ; Given Input ; Function Call
#include <bits/stdc++.h> NEW_LINE using namespace std ; int maximumStonesUtil ( int * arr , int n , int i , vector < int > & dp ) { if ( i >= n ) return 0 ; int & ans = dp [ i ] ; if ( ans != -1 ) return ans ; ans = INT_MIN ; ans = max ( ans , arr [ i ] - maximumStonesUtil ( arr , n , i + 1 , dp ) ) ; if ( i + 1 < n ) ans = max ( ans , arr [ i ] + arr [ i + 1 ] - maximumStonesUtil ( arr , n , i + 2 , dp ) ) ; if ( i + 2 < n ) ans = max ( ans , arr [ i ] + arr [ i + 1 ] + arr [ i + 2 ] - maximumStonesUtil ( arr , n , i + 3 , dp ) ) ; return ans ; } string maximumStones ( int * arr , int n ) { vector < int > dp ( n , -1 ) ; int res = maximumStonesUtil ( arr , n , 0 , dp ) ; if ( res > 0 ) return " Player1" ; else if ( res < 0 ) return " Player2" ; else return " Tie " ; } int main ( ) { int arr [ ] = { 1 , 2 , 3 , 7 } ; int n = sizeof ( arr ) / sizeof ( arr [ 0 ] ) ; cout << maximumStones ( arr , n ) ; return 0 ; }