Optimal game strategy

#1

can you please suggest me the approach , i m not able to think about it .


this is my code

#2

Hi Vikash,
In this question you need to find the maximum coins Piyush can have.
Sample Test Case:
4
1 2 3 4
Piyush->4 , Nimit->3, Piyush ->2, Nimit ->1
Piyush gets maximum of 6 coins.

Since both players play optimally this means, both will choose the maximum coins available to them.
Similarly, see this test case:
4
4 15 3 2
Case 1: Piyush->4, Nimit -> 15 , Piyush ->3 , Nimit ->2
Case 2: Piyush -> 2, Nimit ->4 , Piyush ->15 , Nimit ->3
In case 2 Piyush can have maximum 17 coins.

Try to implement a recursive solution or use a 2D Matrix approach.

#3
#4

doubts are mentioned in the code as commented

#5

Hi Vikash,
in q1 we basically store the ith array value and the minimum of recursive function of (i+2,j)th and (i+1,j-1) values. Because they are playing optimally, Nimit will also choose the max value available to him. And similarly in q2 we take what happens if Piyush first takes the jth value and the min of recursive functions. After that we take the max of coins available and storing it because we may encounter the same values of i and j again. That’s why we have put this condition before:
if(dp[i][j]!=-1) {
return dp[i][j];
}
if the value exists we will return the value and save the recursive calls.

#6

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.