題目
解題方案1：
整理一下規(guī)則：
Alex转锈、Lee兩個人，Alex先手楚殿，Lee后手撮慨。
每次只能拿 第一堆 或者 最后一堆
兩個人拿取的策略 都是最優(yōu)的 都為了打敗對方-
方程：
設 i 為第一堆石子下標，j 為最后一堆石子下標
如果 先手 選擇 i，則后手只能選擇 i+1 或者 j
如果 先手 選擇 j砌溺，則后手只能選擇 i 或者 j-1則先手與后手石子堆的差為：
piles[i] - opt(piles, i+1, j) 或者 piles[j] - opt(piles, i, j-1)
opt(piles, i, j) 的意思是從piles數(shù)組里下標 i 到 j 中選
取石子堆的最佳組合影涉。
因為中間選擇過程我們不清楚，所以可以用遞歸去窮舉规伐。最終結果只要大于0我們就認為先手勝了
代碼如下：
i = 0
j = len(piles)
def opt(piles, i, j):
if i==j:
return piles[i]
if j>i:
return max( piles[i] - opt(piles, i+1, j),
piles[j] - opt(piles, i, j-1) )
return opt(piles, i, j) > 0
解題方案2：
能用遞歸的基本都能用遞推去解決蟹倾，遞推的過程也就是動態(tài)規(guī)劃。筆者是這么理解的猖闪，不一定正確鲜棠，因為本人覺得遞推和動態(tài)規(guī)劃都是遞歸的一個逆過程，遞歸是 從問題最終出發(fā)培慌，而遞推和動態(tài)規(guī)劃都是 從問題的開始出發(fā)豁陆。
具體怎么想到解題的思路，其實我也不知道吵护『幸簦可能題做多了就能知道吧，我也是看了別人的答案想了很久才想明白何址。
解題思路里逆，方案一講講述過的就不再累述了
- 既然是從 問題的開始出發(fā)，那就從游戲開始的第一步來用爪， 這里的 游戲開始 準確的來說應該是從遞歸的最后一步開始原押。一開始還是很難理解的，多想想就能明白之中的奇妙了偎血。
2.方案一遞歸到底的時候只有一個石子堆诸衔，即i=j的情況，然后會不斷上升到兩個石子堆颇玷，三個石子堆取最佳博弈的情況笨农，拿leetcode第一個例子[5,3,4,5]來說的話：
遞歸是考慮了只剩下單獨石子堆的情況： [5] [3] [4] [5]
剩下兩個石子堆的情況：[5,3] [3,4] [4,5]
剩下三個石子堆的情況：[5,3,4] [3,4,5]
最后全集的情況：[5,3,4,5]
我們需要做的就是 自底而上的把最佳博弈情況求出來 因為單獨石子堆的情況最佳博弈情況 是 兩個石子堆里求出最佳博弈情況的基礎，以此類推帖渠。 - 最佳博弈情況方程 （狀態(tài)方程）：
與遞歸的方程是一樣的：
max( piles[i] - opt(), piles[j] - opt() )
求 先手 在當前狀態(tài)下的選擇的石子堆減去 之前兩者博弈的石子差（這個過程是累計的來得谒亦，即我們要每次記住當前人選擇的石子與后者選擇的石子差）。
舉個例子：
因為遞歸最后一步是后手選擇空郊，轉為遞推和動態(tài)規(guī)劃的話份招，后手是第一步。
設A為 先手狞甚， B為 后手
[5,3,4,5]
假設A選擇了第一個5锁摔，則B可以選擇3或者5，為了得到最佳博弈哼审，B會選擇5谐腰，此時的opt就為5孕豹。因為A選擇了5，此時的opt就是5-5=0十气。
接下來A肯定選擇4励背， 則B就只能選擇3了，B選擇后的最佳博弈結果是3-0=3砸西，A選擇后的最佳博弈結果就是4-3=1椅野。
這里是需要好好理解一下的。
3.因為最佳博弈結果是要被記錄下來然后被后者使用的籍胯，就是為了避免遞歸過程中重復計算一樣的子過程。
考慮到有兩個變量選最左邊i還是選最右邊j离福，這里就構建二維數(shù)組opt[N][N]來記錄了杖狼。N為piles數(shù)組的長度。
opt[i][j]是用來記錄所有子問題的最佳博弈結果妖爷，因此就有在方案2上面說的所有情況蝶涩。這就是用二維數(shù)組記錄的原因。
opt[1][3]表示piles[1]到piles[3]中的最佳博弈結果絮识。
從單個情況opt[N][N]開始推到全集opt[0][N], 然后這個opt[0][N]就是我們需要求得的最后結果绿聘。
代碼如下:
上面談到的opt改成了dp
dp = [ [0 for _ in range (0,length)] for _ in range (0,length)]
for i in range (0,length):
dp[i][i] = piles[i]
for i in range (length-2,-1,-1):
for j in range (i+1,length):
dp[i][j] = max( piles[i] - dp[i+1][j], piles[j] - dp[i][j-1] )
return dp[length-1][length-1] > 0
