In Optimal game strategy-1 only 1 test case is passing

#1

why other test cases are not passing?Please check my code

#2

https://ide.codingblocks.com/s/192007 is my code id

#3

Use DP to solve this problem

#4

First try and solve Optimal Game Strategy-1. The move on to this question.

#5

same is the problem with Optimal game strategy-2

#6

Optimal Game Strategy-1 can be solved by using recursion only.
But the other one will be solved using DP.

#7


Check this code for first part and tell me if you are able to understand it.

#8

why are we are taking min in line 10 and line 11 ??

#9

Here is the explanation for the recurrence relations.
Coins can be picked from either end. So we will have two values - one when coin is picked from the start and the other when coin is picked from the end. And we will return the maximum of the two values.
Let the two values be a and b, v be our array and s and e be the starting and ending indices respectively (s = 0 and e = n-1 initially).
maxvalue is the function name.
a = v[s] + min( maxvalue(v,s+2,e), maxvalue(v,s+1,e-1) );
b = v[e] + min( maxvalue(v,s+1,e-1), maxvalue(v,s,e-2) );
a is the value when the first player picks the coin from the start. So v[s] is added. Our array is from s+1 to e now. If the second player picks from the start, our search space becomes s+2 to e now and the first player will be left with maxvalue(v,s+2,e). And if he picks from the end, our search space becomes s+1 to e-1 and the first player will be left with maxvalue(v,s+1,e-1). Both players play optimally, so the second player will leave the minimum of the two values for the first player. Hence the first recurrence relation for a.
We can form the second recurrence relation for b similarly.
And finally we will return max(a,b).