Problem with Optimal Game Strategy 1

#1

I tried two solutions for this problem, both of them are passing the sample test case but none of them is a successful solution.

All test cases failing:- https://ide.codingblocks.com/s/182821

One test case passed:- https://ide.codingblocks.com/s/182822

Can anyone tell me what am I doing wrong here ?

#2

Hi rahul,
You are using greedy method to solve the problem, but this question needs dynamic programming, like both the players play optimally, so u need to store the values for each move and try to maximize the difference by which Piyush wins

#3

In case u do not know how to write the top down DP approach do comment i`ll help u out

#4

Hi Chhavi, In solution 1 above I am using a dp approach whereas in solution 2, I am using a greedy approach in which 1 test case is passing. It’ll be great if you can have a look at my dp solution and tell me the issue with that.

#5

Hey, the dp approach needs to be modified
basically since both are playing optimally

i first choose greater of a[i] or a[j]
then
then other person chooses in a way that any future move by me gains me minimum profit so bascially he`ll allow me to choose

cond1 = a[i] + min( fn(i+2 , j ) , fn ( i+1 , j-1))
cond2 = a[j] + min( fn( i+1 , j -1 ) , fn(i, j-2))

now since u need to play with max value
choice max( cond1 , cond2)

#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.