"""
博弈问题，也称为俩海盗分宝?，俩?拿硬币的问题，其解法也是动态规划
dp数组的含义：
dp[i][j].fir 表?，对于 piles[i...j] 这部分?头堆，先?能获得的最?分数。
dp[i][j].sec 表?，对于 piles[i...j] 这部分?头堆，后?能获得的最?分数。
举例理解?下，假设 piles = [3, 9, 1, 2]，索引从 0 开始
dp[0][1].fir = 9 意味着：?对?头堆 [3, 9]，先?最终能够获得 9 分。
dp[1][3].sec = 2 意味着：?对?头堆 [9, 1, 2]，后?最终能够获得 2 分。
dp数组的转移方程：
dp[i][j].fir = max(piles[i] + dp[i+1][j].sec, piles[j] + dp[i][j-1].sec)
dp[i][j].fir = max( 选择最左边的?头堆 , 选择最右边的?头堆 )
# 解释：我作为先?，?对 piles[i...j] 时，有两种选择：
# 要么我选择最左边的那?堆?头，然后?对 piles[i+1...j]但是此时轮到对?，相当于我变成了后?；
# 要么我选择最右边的那?堆?头，然后?对 piles[i...j-1]但是此时轮到对?，相当于我变成了后?。
if 先?选择左边:
dp[i][j].sec = dp[i+1][j].fir
if 先?选择右边:
dp[i][j].sec = dp[i][j-1].fir
# 解释：我作为后?，要等先?先选择，有两种情况：
# 如果先?选择了最左边那堆，给我剩下了 piles[i+1...j]
# 此时轮到我，我变成了先?；
# 如果先?选择了最右边那堆，给我剩下了 piles[i...j-1]
# 此时轮到我，我变成了先?。
dp的base case:
当i==j时：
dp[i][j].fir = piles[i]
dp[i][j].second = 0
"""
class Pair(object):
def __init__(self, fir, sec):
self.fir = fir
self.sec = sec
def stone_game(piles):
n = len(piles)
dp = [[Pair(0,0) for _ in range(n)] for _ in range(n)]
for i in range(n):
dp[i][i].fir = piles[i] #base case
dp[i][i].sec = 0 #base case
for i in range(n-1, -1, -1):
for j in range(i + 1, n):
#状态转移方程
left = piles[i] + dp[i + 1][j].sec
right = piles[j] + dp[i][j - 1].sec
if left > right:
dp[i][j].fir = left
dp[i][j].sec = dp[i + 1][j].fir
else:
dp[i][j].fir = right
dp[i][j].sec = dp[i][j-1].fir
res = dp[0][n - 1]
return res.fir - res.sec