I have the following task: Positive integers N (2≤N≤100) are written. Each number doesn`t exceed 200. Two players play. For each move, you can cross out the extreme number either on the left or on the right. The crossed out number is added to the player's score. N - even. The first player starts the game. It is necessary to withdraw the maximum possible amount of points for the first player, provided that the opponent plays the best.

IN: The first line of the input file contains one number N. The next N lines contain the initial series of numbers, one number per line.

6
4
7
2
9
5
2

OUT:

18

I understand that the problem is solved by dynamic programming. I`ll write the code myself, but is it possible to describe in general terms the strategy?

CodePudding user response：

With dynamic programming tabulation you can start from the end of the game where only one value is left "on the table". Keyed by the index of that value, register how much the player that has the next move can score. Obviously that score is equal to that value itself. The other player scores 0.

Then extend the "slice" of values with one more: for each consecutive pair consider the current player can take either one. In both cases we end up with a state that is already tabulated, and which gives the best score for the opponent. You can increase the relevant score with the value that was taken first and can see which of the two moves was best for the playing player. Forget about the other move and so get a new table, again by index of the left most value on the table.

Keep extending the slice like that, always building on top of the scores that were tabulated for the previous slice-length.

Finally you will derive the scores and best move for the whole series of numbers.