this is a two player game. initially there
are n integer numbers in an array and
players a and b get chance
to take them alternatively. each player can take one or more numbers from the
left or right end of the array but cannot take from both ends at a time. he can
take as many consecutive numbers as he wants during his time. the game ends when
all numbers are taken from the array by the players. the point of each player is
calculated by the summation of the numbers, which he has taken. each player
tries to achieve more points from other. if both players play optimally and
player a starts the game then how much more point can
player a get than player b?
the input consists of a number of cases. each case starts with a line
specifying the integer n (0 < n ≤100),
the number of elements in the array. after that, nnumbers
are given for the game. input is terminated by a line
where n=0.
output
for each test case, print a number, which represents the maximum difference
that the first player obtained after playing this game optimally.
題目大意：給n個數，兩個人輪流取數，可以從左往右或從右往左取任意多個。兩個人都希望自己的取得的數的總和盡量大，都采取最優政策，問第一個人能比第二個人取得的數多多少。
思路：很容易可以想到一個o(n^3)的dp，用dp[i][j]代表隻剩下a[i..j]的數，先手可以取得的最大值，此時後手取得的最大值為sum[i..j]
- dp[i][j]。
那麼狀态轉移方程為：dp[i][j] = max(sum[i..j], sum[i..j] - min(dp[i+1][j],
dp[i+2][j]……), sum[i..j] - min(dp[i][j - 1], dp[i, j - 2])。
輸出結果為2 * dp[1][n] - sum[1..n]。
代碼（0.026s）：
view code
這個dp還有優化的餘地，觀察狀态轉移方程可以發現，dp[i][j]使用了min(dp[i+1][j],
dp[i+2][j]……)，而dp[i+1][j]=min(dp[i+2][j], dp[i+3][j]……)，有重複的部分。
于是我們可以用l[i][j]記錄max(dp[i][j], dp[i+1][j],
dp[i+2][j]……)，即從左往右取的後手最小值，則sum[i..j] - min(dp[i+1][j],
dp[i+2][j]……)可以寫成sum[i..j]-l[i+1][j]。每次更新l[i][j] = min(dp[i][j], l[i+1][j])。
同理用r[i][j]記錄從右往左取的後手最小值。
至此dp優化至o(n^2)。
代碼（0.015s）：