I am not understanding the recurrence relation

#1

dp(i,j,1)=max(a[i]+dp(i+1,j,0),a[j]+dp(i,j-1,0))
dp(i,j,0)=max(a[i]+dp(i+1,j,1),a[j]+dp(i,j-1,1))
return dp(i,j,1)-dp(i,j,0)

i think this also works…can this be a recuurence relation

#2

Hello Neha, I doubt this approach!
this doesn’t accounts that one player starts first and another player starts second!
so just compute answer for first player, then definitely answer for second player is
total_sum-answer_of_player_1.
and so final answer is 2*answer_of_player_1-total_sum.

#3

dp(i,j,1) it self says 1st player has to start (the 1 (3rd parameter) )and dp(i,j,0) is for 2 nd

#4

and i understand your logic too…but i am not understanding why cant i write it like this

#5

Yes but you can’t do dp(i,j,0) then as this means you consider coins from index i to j when its player 2’s turn!(you already considered it for player 1 so either subtract dp(i+1,j,0) or dp(i,j-1,0) )
this is meaningless as you consider both players starting first!!!
your code should give answer as 0.

#6

ok got it thanks!!!

#7

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.