https://ide.codingblocks.com/s/201650 – code link
I used recursion approach and I know it is a DP problem from discussions but what is the error in my recursive code approach
Every test case gives wrong answer,even though all sample inputs and other inputs I can think of gives right output,Please Help
Optimal Game Strategy-1 can be solved by simply using recursion. There is a specific approach to solve this question. Here it is -
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).
1 Like
Hi,
Thanks for the indepth approach , all test cases got passed
code – https://ide.codingblocks.com/s/201737