tried this brute-force approach working for only Test Case 2
Optimal game strategy 1
Hey @bhattanurag426 greedy won’t work for this problem.
So to tell you how this problem works is let me explain it to you with an example
Suppose in my array I have
100 1000 10 90
Here I will pick 90 first so that opponent don’t get access to 1000 and he will pick 100 then I pick 1000
and he picks 10 so answer is 1090
There are two choices:
- The user chooses the ‘ith’ coin with value ‘Vi’: The opponent either chooses (i+1)th coin or jth coin. The opponent intends to choose the coin which leaves the user with minimum value .
i.e. The user can collect the value Vi + min(F(i+2, j), F(i+1, j-1) ) .
- The user chooses the ‘jth’ coin with value ‘Vj’: The opponent either chooses ‘ith’ coin or ‘(j-1)th’ coin. The opponent intends to choose the coin which leaves the user with minimum value, i.e. the user can collect the value Vj + min(F(i+1, j-1), F(i, j-2) ) .
We are sending minimum of i+2,j and i+1,j-1 cause both players are planing to play optimally So both are ready to cut each other points by sending minimum value to them and reserving maximum value for themselves.
sir still didn’t get it.
Check this->
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.