Coins in a Line

1) 题意：

Input 是一个length为偶数的array，两人轮流按照只能够拿array头尾的规则拿这个array的数字，每次拿1个换另一个人拿，直到拿完array。你和对手都很聪明知道怎么取和最大。

问题1:如果让你玩儿你先拿还是后拿？
问题2:如果你先拿，计算你能拿的最大和。

2) 算法：

问题1: 谁先走问题

考虑先走。如果先走，有没有一个策略可以不输（赢或者平手）。注意到题目条件Input长度是偶数。两个玩家拿的数字个数一定是一样的。那么举个例子：2，4，3，1，5，2 。我的选择是第1个，另一人选第2个，我可以选第3个，他选第6个，我选第5个，他拿最后第4个。在这个过程中，我可以掌控我只拿奇数位的数字，他只拿偶数位的数字。我也可以一开始选择第6个，那么我就是要所有偶数位。因此，我可以比较Sum（奇数位）和Sum（偶数位），从而选择怎么走。

如果length为奇数，怎么做？

当length为奇数的时候，去掉1个，length就成了偶数。这个时候，你可以算一下Sum（奇数位）和Sum（偶数位）。第二个走的人定会选最大那个，
因此你需要计算
(nums[0］或者 nums[n-1]) +min(sum(odd),sum(even)) 和 max(sum(odd),sum(even))的关系。
如果前者大，你先走。
如果后者大，你后走。

这个解法可以保证不输。
但无法计算出最优解。

问题2: 如果你先走，最优解

这种你一步我一步的题目，让人想到了miniMax问题以及DP
miniMax：the two players are called maximizer and minimizer. The maximizer tries to get the highest score possible while the minimizer tries to get the lowest score possible while minimizer tries to do opposite.

http://www.geeksforgeeks.org/minimax-algorithm-in-game-theory-set-1-introduction/

不是特别符合本题。对手的目标是最大化他的sum

DP：The remaining coins are { A_i … A_j } and it is your turn. Let P(i, j) denotes the maximum amount of money you can get 

P(i,j) = Max(A[i] + 对手走后你再走的sum, A[j] + 对手走后你再走的sum)

因为对手也超级聪明，因此他一定会走一步使得你要走的时候，聪明的你一定走最小

所以假设你选了A[i], 对手从{Ai+1 ... Aj} 选，他会选A[i+1]如果当你走的时候 {Ai+2 ... Aj}比{Ai＋1 ... Aj－1}小。或者他选A[j]，如果比较结果相反。

因此：P(i,j) = Max(

                         A[i] +Min(P(i+2,j), P(i+1,j-1)), 

                         A[j] + Min(P(i+1,j-1), P(i,j-2)))

所以可以用dp来做。注意从内向外计算P(i,j)。(You would first compute P(1,1), P(2,2), … P(n, n) and work your way up).

reference from http://articles.leetcode.com/coins-in-line/