Optimal game strategy -1

#1

the max value piyush can win is 7 int the folllowing way :

  1. first turn of piyush

piyush picks 4

  1. first turn of nimit ’

if nimit picks 3 then max value piyush can win is 6

otherwise piyush can pick 3 in his second turn and make total of 7…

#2

Hey Soorya, in the problem both players play optimally, hence when it’s your turn, you try to maximize your score and when it’s opponent’s turn ,he tries to minimise your score!
so this way answer for sample input is 6 only

#3

i am applying the strategy to take either values at odd or values at even depending upon which gives max answer but this strategy is also showing up incorrect for just one testcase

#4

Well that seems to be greedy and that’s again not correct!
use DP where dp[i][j] refers to state when coins are remaining from [i,j] (means that 0 to i-1 and j+1 to n-1 are already taken!)
so when its your turn dp[i][j] = max(a[i] + dp[i+1][j],a[j] + dp[i][j-1])
and its min(…) in case when its your opponents turn!
try to do this either via bottom up or top down

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.