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