博弈问题

 1 状态显然有三个：开始的索引 i，结束的索引 j，当前轮到的人
 2 dp[i][j][fir or sec]
 3 其中：
 4 0 <= i < piles.length
 5 i <= j < piles.length
 6 
 7 n = piles.length
 8 for 0 <= i < n:
 9     for i <= j < n:
10         for who in {fir, sec}:
11             dp[i][j][who] = max(left, right)
12 
13 dp[i][j].fir = max(piles[i] + dp[i+1][j].sec, piles[j] + dp[i][j-1].sec)
14 dp[i][j].fir = max(    选择最左边的石头堆     ,     选择最右边的石头堆     )
15 # 解释：我作为先手，面对 piles[i...j] 时，有两种选择：
16 # 要么我选择最左边的那一堆石头，然后面对 piles[i+1...j]
17 # 但是此时轮到对方，相当于我变成了后手；
18 # 要么我选择最右边的那一堆石头，然后面对 piles[i...j-1]
19 # 但是此时轮到对方，相当于我变成了后手。
20 
21 if 先手选择左边:
22     dp[i][j].sec = dp[i+1][j].fir
23 if 先手选择右边:
24     dp[i][j].sec = dp[i][j-1].fir
25 # 解释：我作为后手，要等先手先选择，有两种情况：
26 # 如果先手选择了最左边那堆，给我剩下了 piles[i+1...j]
27 # 此时轮到我，我变成了先手；
28 # 如果先手选择了最右边那堆，给我剩下了 piles[i...j-1]
29 # 此时轮到我，我变成了先手。
30 
31 base case:
32 dp[i][j].fir = piles[i]
33 dp[i][j].sec = 0
34 其中 0 <= i == j < n
35 # 解释：i 和 j 相等就是说面前只有一堆石头 piles[i]
36 # 那么显然先手的得分为 piles[i]
37 # 后手没有石头拿了，得分为 0