題目連結(jié)：
題目意譯：
Alice 和 Bob 輪流玩著一個遊戲，並由 Alice 作為先手。
現(xiàn)在有著 n 個石頭排列於一列。每個玩家的回合中，他們可以移除列中最左邊或是最右邊的石頭並且得到等同於剩下石頭之?dāng)?shù)值總和的分?jǐn)?shù)。贏家為當(dāng)沒有石頭可以移除時，此時分?jǐn)?shù)最高者。
Bob 發(fā)現(xiàn)他必定會輸?shù)暨@個遊戲（可憐的 Bob，他每次都會輸），所以他決定將分?jǐn)?shù)差距最小化。而 Alice 的目標(biāo)則是將分?jǐn)?shù)差最大化。
給定一整數(shù)陣列 stone 其中 stones[i] 代表著從左邊數(shù)來第 i 顆石頭的數(shù)值，回傳在 Alice 與 Bob 按最佳策略遊玩下的分?jǐn)?shù)差。
限制：
n == stones.length
2 ≦ n ≦ 1000
1 ≦ stones[i] ≦ 1000
範(fàn)例測資：
範(fàn)例 1：
輸入： stones = [5,3,1,4,2]
輸出： 6
解釋：
- Alice 移除 2 並得到 5 + 3 + 1 + 4 = 13 點分?jǐn)?shù)。 Alice = 13 、 Bob = 0 、 stones = [5,3,1,4] 。
- Bob 移除 5 並得到 3 + 1 + 4 = 8 點分?jǐn)?shù)。 Alice = 13 、 Bob = 8 、 stones = [3,1,4] 。
- Alice 移除 3 並得到 1 + 4 = 5 點分?jǐn)?shù)。 Alice = 18 、 Bob = 8 、 stones = [1,4] 。
- Bob 移除 1 並得到 4 點分?jǐn)?shù)。 Alice = 18 、 Bob = 12 、 stones = [4] 。
- Alice 移除 4 並得到 0 點分?jǐn)?shù)。 Alice = 18 、 Bob = 12 、 stones = [] 。
分?jǐn)?shù)差為 18 - 12 = 6 。
範(fàn)例 2：
輸入： stones = [7,90,5,1,100,10,10,2]
輸出： 122
解題思維：
我們可以利用動態(tài)規(guī)劃（Dynamic Programming，DP）的精神得到所求分?jǐn)?shù)差。
可以看到當(dāng)石頭只有一顆時，分?jǐn)?shù)差顯而易見地是 0 ；兩顆石頭 x 、 y ，分?jǐn)?shù)差即是兩顆石頭中最大的（max(x, y)）。
三顆石頭 x 、 y 、 z 時，因為我們已經(jīng)知道兩顆石頭的情況，所以 Alice 取左邊的石頭將得到分?jǐn)?shù)差 (y + z) - (max(y, z)) 、 取右邊的石頭將得到分?jǐn)?shù)差 (x + y) - (max(x, y)) 。哪個值較大，即是所求（因為 Alice 與 Bob 都按照最佳策略遊玩）。
所以 n 顆石頭的時候可以從 n - 1 顆（取左邊、取右邊）推得。因此令 D[i][j] 為 stones[i] ～ stones[j] 所形成的遊戲局面（為了方便，stones 的索引值從 1 開始），我們可以得到遞迴式：
D[i][j] = 0，當(dāng) i = j 時；
D[i][j] = max((P[j] - P[i]) - D[i+1][j], (P[j-1] - P[i-1]) - D[i][j-1])
其中 P[i] 代表著 stones 前 i 顆石頭之值總和（而 P[0] = 0），即 P 為 stones 的前綴和（Prefix Sums）陣列。利用前綴和我們可以快速地求得某個區(qū)段的總和（如這題）。
因此所求即為 D[1][n] 。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
