Optimal Game Strategy-I (Recursion Challenges)

#1

Here is my code,

I am getting 3 wrong answers while submitting.

#2

At first look , this looks like a Greedy problem but it is clearly not so. This can clearly be observed in a simple testcase like
4
5 4 8 6
Clearly , we would need an optimal solution for this. At each instance we would need to consider two possibilities that we can pick the first as well as the last element of the remaining array. Both these possibilities give rise to two more possibilities depending on the other player. Since the second player plays optimally and try to minimise our score. So overall we have two possibilities at each instance.
For the first possibility , where we could pick the first element , the other player will pick the next element from the side that would minimise our total score.
Similarly , for the second possibility , where we can pick the last element , the other player would still pick the next element from the side that would minimise our total score.
We entertain both these cases and take the maximum result of the two and return that result.
We take two pointer variables , say ā€˜iā€™ and ā€˜jā€™ which each represent the starting and the ending point of the remaining array currently in consideration. We work till the two pointers cross each other.

1 Like
#3

u can refer my code https://ide.codingblocks.com/s/610638

1 Like
#4

do u still have any doubts??

1 Like
#5

Just one doubt.
Why did you use ā€œminā€ value while calculating opt1 and opt2 ??

#6

because say we picked first or last item in our chanceā€¦ next chance is of other playerā€¦ so other player would also try to have max value. in this we have 2 options and we choose min of 2 as player 2 would also try to get max total

1 Like
#7

Hmm
I kinda get it.
But it is a bit difficult to get your head around it.

#8

yesā€¦ u would get a better insight of this ques in dynamic programming sectionā€¦ there sir has made a video lecture also on the sameā€¦

1 Like
#9

Okay okay
Thank you so much

#10

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.