2 wrong answers..whats wrong with the approach?

#1

code-https://ide.codingblocks.com/s/189113
what is wrong with the approach i am using dp but its showing tle in one case and 2 wrong cases.

#2

@amitrao
No need to use pairs. You only have to compute the max score for the first player. Also , you are not considering the fact that the other player also plays optimally. Hence at each instance , the other player will try to minimise our score.
If you are picking the first element , make two recursive calls as the second player has possibility to choose the first of the remaining array or the last of the remaining array. Since the other play tries to minimise our score , pick the minimum of these two results.
min( optimalGame(i+2,j) , optimalGame(i+1,j-1) ) ;

Similarly , we can also pick the last element. Pick the minimum of the two consequent recursive calls as well. Add the price of picking first and last coins as well to their corresponding choices. Finally pick the max of these two.

1 Like