Optimal game strategy

#1

I was unable to pass the 5th test case. Please give any improvement in the solution or any other solution
code link : https://ide.codingblocks.com/s/213338

#2

Hi @SWIFTY,
this is a dp question.
u need to apply recursion on whether piyush choose first or last coin and the combine it with dp to optimise it.
In the present scenerio, ur code is not accounting for all ways to take coin possible.
Hope dis helps.
If u still hv any doubts, feel free to post them here

#3

i don’t know how to use dp for this problem. But as piyush is going first he will always win since he will be collecting all coins at even or odd position which ever is greater i did same thing in the implementation

#4

@SWIFTY,
u cant apply greedy approach in dis.
eg.
4,2,9,5
in dis, piyush should first start with 4, then pick 9 in his second turn and win the game.
But if piyush pick 5 first, other person will pick 9 and will surely win d game.
so, u have to take all cases whether to pick from right or left.
Hope dis helps

#5

@SWIFTY
use dp relation like dis:
int x=A[s]+min(game(A,s+2,e,n),game(A,s+1,e-1,n));
int y=A[e]+min(game(A,s+1,e-1,n),game(A,s,e-2,n));
and store max of x,y in dp[n]