為了預(yù)防老年癡呆順便維持手感咱筛，一個(gè)程序員應(yīng)當(dāng)時(shí)不時(shí)刷幾道算法題挑戰(zhàn)一下彼妻。記得之前上算法課的時(shí)候嫌佑，我一直認(rèn)為動(dòng)歸的題都是最簡(jiǎn)單的——套路嘛豆茫，遇事不決歸一下（侨歉？）同時(shí)，動(dòng)歸的過程總會(huì)給人一種優(yōu)雅的感覺：有的問題看上去那么復(fù)雜揩魂，仿佛一團(tuán)亂麻幽邓，但抽絲剝繭，又總能找到最簡(jiǎn)單的那個(gè)火脉。一生二牵舵，二生三，三生萬(wàn)物倦挂，大道歸一畸颅，是哲學(xué)的優(yōu)雅。感謝計(jì)算機(jī)方援，讓我們不用自己從1數(shù)到萬(wàn)没炒，只要敲下一個(gè)簡(jiǎn)單的for循環(huán)，嘬口咖啡的功夫不到犯戏，cpu就幫你把計(jì)算的臟活累活干完送火，正確的答案靜靜地顯示在控制臺(tái)等你審閱。

當(dāng)然了先匪，對(duì)于題目來(lái)說种吸，自然不能都沿用同樣的套路。一些帶著稍許“變形”的題目呀非，能讓你在識(shí)破其中的馬甲時(shí)被刺激出更多的多巴胺坚俗。這篇廢話要記錄的就是這樣一個(gè)不那么標(biāo)準(zhǔn)的動(dòng)歸題：

LeetCode486. 預(yù)測(cè)玩家

給定一個(gè)表示分?jǐn)?shù)的非負(fù)整數(shù)數(shù)組。 玩家 1 從數(shù)組任意一端拿取一個(gè)分?jǐn)?shù)岸裙，隨后玩家 2 繼續(xù)從剩余數(shù)組任意一端拿取分?jǐn)?shù)坦冠，然后玩家 1 拿，…… 哥桥。每次一個(gè)玩家只能拿取一個(gè)分?jǐn)?shù)辙浑，分?jǐn)?shù)被拿取之后不再可取。直到?jīng)]有剩余分?jǐn)?shù)可取時(shí)游戲結(jié)束拟糕。最終獲得分?jǐn)?shù)總和最多的玩家獲勝判呕。

給定一個(gè)表示分?jǐn)?shù)的數(shù)組倦踢，預(yù)測(cè)玩家1是否會(huì)成為贏家。你可以假設(shè)每個(gè)玩家的玩法都會(huì)使他的分?jǐn)?shù)最大化侠草。

簡(jiǎn)單來(lái)說辱挥，可以看做一個(gè)先手問題。兩個(gè)人依次選數(shù)組頭尾任意一個(gè)數(shù)边涕，看誰(shuí)最后拿的數(shù)字和最大晤碘，同時(shí)兩個(gè)人都是拿數(shù)字高手，訓(xùn)練有素功蜓，一般不會(huì)輸除非必須輸园爷。然后根據(jù)數(shù)組判斷先手能不能贏。為了簡(jiǎn)便式撼，在這道題中平局的情況視為先手玩家獲勝童社。

不知道正常人類是否存在這樣的拿數(shù)字高手，反正我不是著隆。不過沒關(guān)系扰楼，現(xiàn)代社會(huì)的人類都知道，一切繁瑣的計(jì)算交給計(jì)算機(jī)嘛美浦。對(duì)于我來(lái)說弦赖，我能一眼看穿的牌面是什么呢：

? 1. 數(shù)組是空的——先手勝。

? 2. 數(shù)組只有一個(gè)數(shù)字——先手勝浦辨。

? 3. 數(shù)組只有兩個(gè)數(shù)字——先手勝蹬竖。

那么，當(dāng)數(shù)組的大小大于2荤牍，誰(shuí)贏呢案腺？

讓我來(lái)假裝自己是一個(gè)拿數(shù)字高手：假設(shè)我可以算出來(lái)這個(gè)數(shù)組我先拿的情況下我最多可以拿到的和是多少，那么我也可以算出來(lái)我拿了頭或者尾后康吵，我的對(duì)手面對(duì)剩下的數(shù)組最多可以拿到多少劈榨。

聽起來(lái)很繞很暈對(duì)不對(duì)？我也覺得晦嵌，所以我們成不了拿數(shù)字高手同辣。不過沒關(guān)系，很繞的邏輯寫成代碼卻很簡(jiǎn)單：

其中惭载，`nums`為數(shù)組旱函，`dp[i][j]`為數(shù)組從 `i` 到 `j` 的子數(shù)組中先手與后手得分的差值（即先手得分-后手得分）。這行代碼妙在哪里呢描滔？我們?cè)倏匆谎垲}目：

給定一個(gè)表示分?jǐn)?shù)的非負(fù)整數(shù)數(shù)組棒妨。 玩家 1 從數(shù)組任意一端拿取一個(gè)分?jǐn)?shù)，隨后玩家 2 繼續(xù)從剩余數(shù)組任意一端拿取分?jǐn)?shù)含长，然后玩家 1 拿券腔，…… 伏穆。每次一個(gè)玩家只能拿取一個(gè)分?jǐn)?shù)，分?jǐn)?shù)被拿取之后不再可取纷纫。直到?jīng)]有剩余分?jǐn)?shù)可取時(shí)游戲結(jié)束枕扫。最終獲得分?jǐn)?shù)總和最多的玩家獲勝。

題目中反復(fù)出現(xiàn)玩家1辱魁，玩家2的概念烟瞧，很容易讓讀者陷入一種思維的禁錮：去思考玩家1和玩家2在拿數(shù)字的時(shí)候各自的路徑選擇問題。但實(shí)際上呢染簇？這個(gè)游戲的本質(zhì)是一個(gè)交替先手的問題参滴，也就是說，不要再管玩家1還是玩家0還是玩家甲乙丙丁了剖笙！想象一個(gè)精分的拿數(shù)字高手自己和自己玩卵洗，他要做的就是讓`dp[i][j]`盡可能的大请唱，然后看看`dp[0][n-1]`（`n`為數(shù)組大忻诌洹）最后是不是大于`0`就完事了！是不是很妙十绑？表面上是兩個(gè)玩家在玩拿數(shù)字聚至，實(shí)際上你中有我我中有你，你的陰謀也是我的陽(yáng)謀本橙，誰(shuí)也不比誰(shuí)高明扳躬，誰(shuí)也不比誰(shuí)愚鈍，就算你背了愛馬仕甚亭，我只拎著小ck贷币，在這場(chǎng)游戲中，我們的結(jié)局早已確定——猜到了這開頭亏狰，也看穿了這結(jié)尾役纹。