Coins in a line problem

Revision en1, by amr0, 2020-09-25 19:47:36

Hello Codeforcians, I tried to do the famous "coins in a line problem" where two players play a game in which at each turn a player can select one coin from one end of the line of coins (the coins are sorted in a row). The problem then is to determine the guaranteed profit player A can make assuming player A starts first. The coins' values are $$$v_0$$$ to $$$v_{n-1}$$$. My approach was to apply for the recursive DP formula is:

F[i][j] = Max(pref[j]- pref[i] — F[i+1][j]+values[i], F[j-1]-pref[i-1] — F[i][j-1]+values[j])

where pref[i] is the prefix sum of all the coin values $$$v_0$$$ to $$$v_i$$$

However, the DP I found online is F(i, j) = Max(Vi + min(F(i+2, j), F(i+1, j-1) ), Vj + min(F(i+1, j-1), F(i, j-2) ))

Can anyone tell me why approach is wrong?

Thank you

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en3 English amr0 2020-09-25 19:49:02 0 (published)
en2 English amr0 2020-09-25 19:48:40 45 (saved to drafts)
en1 English amr0 2020-09-25 19:47:36 811 Initial revision (published)