How to approach this question?

#1

Kindly help how I can approach this question?

#2

hey sagnik, before answering this question, please tell me whether you are aware of Dynamic Programming or not. Beacuse this question can be done easily with DP.

#3

Yes, I am aware of Dynamic Programming.
But I wanted to code a pure recursive solution. I do not want to opt the bottom up approach. Well if I can figure out the recursive solution (recursive relation) I will be able to implement it using memoization and bottom up approach.
So I wanted help to solve it recursively…
And this problem is also given under Recursion topic.
In fact I have read many articles online on how I can solve this problem. But I was somewhere not very clear with their explanations.
That’s why I thought of posting this doubt.

#4

hey Sagnik, here is an explanation.
Remember both A and B are equally smart and we want A to get maximum.
if coins are indexed from i to j and both have to choose one out of two ends.

case 1: if A chooses a[i], now opponent can choose either a[i+1] or a[j] whatever is maximum out of two. which means A will get Minimum in his next chance based on opponent choice.
case 1.a: if opponent choose a[i+1], player will chose either a[i+2] or or a[j]
case 1.b: if opponent choose a[j], player will chose either a[i+1] or or a[j-1]
So A will get minimum out of case 1.a and case 1.b…as opponent is equally smarter and choose such a coin which give him maximum but minimum to player A.

case 2: if A chooses a[j], now opponent can choose either a[i] or a[j-1] whatever is maximum out of two. which means A will get Minimum in his next chance based on opponent choice.
case 2.a: if opponent choose a[i], player will chose either a[i+1] or or a[j-1]
case 2.b: if opponent choose a[j-1], player will chose either a[i] or or a[j-2]
So A will get minimum out of case 2.a and case 2.a…as opponent is equally smarter and choose such a coin which give him maximum but minimum to player A.

This will give you a recursive case in which final answer is max(case1,case2)

#5

Well I did figure out the logic, but can you provide a partial code or pseudo code for this problem. I am getting stuck while implementing this. Pls write a pseudo code a help…

#6

hey Sagnik, I hope this will help you.

function max_coin( int *coin, int start, int end ):
if start > end:
return 0
int a = coin[start] + min(max_coin(coin, start+2, end), max_coin(coin, start+1, end-1))
int b = coin[end] + min(max_coin(coin, start+1,end-1), max_coin(coin, start, end-2))

return max(a,b)
#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.

1 Like