OJ Board

hi,

i'm trying to solve this problem, but i don't understand what is mean by optimal strategy. is this mean player 2 always choose largest number that can be pick?

thanks for ur kind response.

b3yours3lf wrote:i'm trying to solve this problem, but i don't understand what is mean by optimal strategy. is this mean player 2 always choose largest number that can be pick?

If I remembered correctly the answer for your question is NO. Player can also choose the smaller number if it will give him/her better result at the end of the game.

Hope it helps

This problem can be solved using DP. Let
sum[j] - sum of elements from i-th position till j-th position
f1[j] - first player score on this table
f2[j] - second player score on this table
f2[j]=sum[j]-f1[j].

answer is f1[1][n] and f2[1][n]