Max sum from Coins in a line

Optimal Strategy for a Game : Consider a row of n coins of values v(1) ... v(n), where n is even. We play a game against an opponent by alternating turns. In each turn, a player selects either the first or last coin from the row, removes it from the row permanently, and receives the value of the coin. Determine the maximum possible amount of money we can definitely win if we move first.

Refer here for explanative answer : http://leetcode.com/2011/02/coins-in-line.html

There are n coins in a line. (Assume n is even). Two players take turns to take a coin from one of the ends of the line until there are no more coins left. The player with the larger amount of money wins.

1. Would you rather go first or second? Does it matter?
2. Assume that you go first, describe an algorithm to compute the maximum amount of money you can win.

Consider the two coins the opponent will possibly take, A_i+1 and A_j. If the opponent takes A_i+1, the remaining coins are { A_i+2 … A_j }, which our maximum is denoted by P(i+2, j). On the other hand, if the opponent takes A_j, our maximum is P(i+1, j-1). Since the opponent is as smart as you, he would have chosen the choice that yields the minimum amount to you.

Therefore, the maximum amount you can get when you choose A_i is:

P1 = Ai + min { P(i+2, j), P(i+1, j-1) }

Similarly, the maximum amount you can get when you choose A_j is:

P2 = Aj + min { P(i+1, j-1), P(i, j-2) }

Therefore,

P(i, j) = max { P1, P2 }
        = max { Ai + min { P(i+2, j),   P(i+1, j-1) },
                Aj + min { P(i+1, j-1), P(i,   j-2) } }