难度: Medium
爱丽丝和鲍勃继续他们的石子游戏。许多堆石子 排成一行，每堆都有正整数颗石子 piles[i]。游戏以谁手中的石子最多来决出胜负。
爱丽丝和鲍勃轮流进行，爱丽丝先开始。最初，M = 1。
在每个玩家的回合中，该玩家可以拿走剩下的 前 X 堆的所有石子，其中 1 <= X <= 2M。然后，令 M = max(M, X)。
游戏一直持续到所有石子都被拿走。
假设爱丽丝和鲍勃都发挥出最佳水平，返回爱丽丝可以得到的最大数量的石头。
示例 1：
输入：piles = [2,7,9,4,4] 输出：10 解释：如果一开始Alice取了一堆，Bob取了两堆，然后Alice再取两堆。爱丽丝可以得到2 + 4 + 4 = 10堆。如果Alice一开始拿走了两堆，那么Bob可以拿走剩下的三堆。在这种情况下，Alice得到2 + 7 = 9堆。返回10，因为它更大。
示例 2:
输入：piles = [1,2,3,4,5,100] 输出：104
提示：
1 <= piles.length <= 1001 <= piles[i] <= 104运行时间: 93 ms
内存: 16.4 MB
class Solution:
def stoneGameII(self, piles: List[int]) -> int:
s, n = 0, len(piles)
dp = [[0] * (n + 1) for _ in range(n)]
for i in range(n - 1, -1, -1):
# 后缀和
s += piles[i]
for m in range(1, i // 2 + 2):
if i + m * 2 >= n:
dp[i][m] = s
else:
dp[i][m] = s - min(dp[i + x][max(m, x)] for x in range(1, m * 2 + 1))
return dp[0][1]
这个问题可以通过动态规划来解决。定义 dp[i][m] 为从第 i 堆开始，M 值为 m 时，当前玩家可以获得的最大石子数。s 用来记录从当前堆到最后一堆的石子总数（后缀和）。如果从第 i 堆开始，玩家可以选择拿 1 到 2m 堆的石子，那么 dp[i][m] 就应该是 s 减去后续玩家可能的最小值，即 s - min(dp[i+x][max(m,x)] for x in range(1, m*2+1))。如果 i + m * 2 超出了石子堆的数量，即 i+m*2 >= n，当前玩家可以直接拿走所有剩余的石子，dp[i][m] = s。最终解为 dp[0][1]，即从第一堆开始，M=1 的情况。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def stoneGameII(self, piles: List[int]) -> int:
s, n = 0, len(piles)
dp = [[0] * (n + 1) for _ in range(n)]
for i in range(n - 1, -1, -1):
s += piles[i] # 更新后缀和
for m in range(1, i // 2 + 2):
if i + m * 2 >= n:
dp[i][m] = s # 如果当前玩家可以拿走所有剩余石子
else:
# 计算拿走 1 到 2m 堆石子后的最优解
dp[i][m] = s - min(dp[i + x][max(m, x)] for x in range(1, m * 2 + 1))
return dp[0][1] # 从第一堆石子开始，M=1 的最优解
在这个问题中，`dp[i][m]`表示从第`i`堆石子开始，当`M`值为`m`时，当前玩家可以获得的最大石子数。这是一个两维动态规划数组，其中`i`代表起始堆的索引，`m`代表根据游戏规则中的`M`值，影响玩家可以选择拿走的堆数。`dp[i][m]`的优化目标是最大化从`i`堆开始时玩家的石子收益，考虑到对方玩家的最优策略。
这个计算逻辑基于博弈论中的`最优反应策略`。`s`代表从第`i`堆到最后一堆的石子总数。`s - min(dp[i+x][max(m,x)] for x in range(1, m*2+1))`的计算是为了确定在当前玩家拿走某数量石子后，对手能够获得的最小收益，从而使当前玩家的收益最大化。具体来说，对手在接下来的回合中，根据游戏规则选择`x`堆石子，使得`M`更新为`max(m, x)`，动态规划寻求在所有可能的选择中使对手的收益最小，从而确保当前玩家收益最大。
在代码中，后缀和`s`是通过从数组的末尾开始向前累加实现的。这一过程在循环中`for i in range(n - 1, -1, -1)`逐步执行，每次循环中`s += piles[i]`更新当前的后缀和。后缀和`s`在动态规划中的作用是记录从当前堆`i`开始到最后一堆石子的总数，这是计算当前玩家在任何选择下都能保证的基础石子数，用于与对手可能的最小收益作比较，进而决定最优的拿取策略。
这个结论基于游戏的规则和石子的分布。根据游戏规则，玩家每次可以选择拿取的石子堆数最多为`2m`。如果`i + m * 2 >= n`，意味着从堆`i`开始的剩余石子堆数不足`2m`堆，也就是说，当前玩家在此回合内可以选择拿走所有剩余的石子堆，因为其选择范围覆盖了所有剩余堆。因此，此时`dp[i][m]`就等于剩余石子的总和`s`。