Where does the root of this tree come from?

Question

I am doing a practice question from Midterm Dynamic Programming

The Problem : Consider a row of n numbers a1, ..., an. The numbers are all positive, and n is even. We play a game against an opponent, alternating turns. In each turn, a player selects either the first or last number, removes it from the row, and collects that much money.

For example, if the numbers are 1,2,3,4 , a possible game may look like:

1. Player A takes 4: row is 1,2,3.
2. Player B takes 3: row is 1,2.
3. Player A takes 1: row is 2.
4. Player B takes 2, game over.

Both players ended with a total amount of 5. Note that A could have done better.

(2 pts) Show an example where the greedy algorithm fails to achieve the highest possible amount of money.

Here is the solution to the problem Greedy Sol

In the diagram, does anyone know where the 11, the root of the tree, is coming from? I thought it was the highest possible amount of money but that be 13 here (10 + 3).

Answer 1

If I understand correctly, this diagram represents both players playing optimally. Every value inside the node(rectangle/circle) is the highest possible value the first play can obtain if both players play optimally. After the first step of the first player, there are two possible states {2,10,3} and {1,2,10}. In {1,2,10} it is the second player's turn and if she/he plays optimally, the highest value the first player can obtain is 2 (the second player will remove 10 first to be optimal). However, if the first player remove 1 first (thus the state {2,10,3}), then no matter how the second player remove next, the first player will remove 10 in her/his second turn to be optimal. Thus highest value the first player can obtain is $$\max\{3 + 2, 1 + 10\}=11$$