石子游戏 VIII（博弈类区间DP的进阶变体：取石子堆的博弈最大化差值）

题目描述

两个玩家（Alice 和 Bob）轮流玩游戏，初始有一排 n 堆石子，每堆石子有一个整数价值（可能为负）。游戏规则如下：

1. 玩家可以从当前剩余石子堆的左侧（即最左边）或右侧（即最右边）取走一堆石子，获得这堆石子的价值（作为自己的得分）。
2. 取走石子堆后，石子序列缩短，下次从新的左右两端继续选择。
3. 游戏进行直到所有石子堆被取完。
4. Alice 先手，Bob 后手，两人都采取最优策略，目标是最大化自己的总得分与对方总得分的差值。

问题：假设 Alice 先手，在两人都绝顶聪明的情况下，求 Alice 能获得的最大得分差值（Alice 得分 − Bob 得分）。

输入输出示例

• 输入：stones = [3, 2, 5, 4]
• 输出：6

解释：
一种最优玩法：

• Alice 取左侧 3，剩下 [2, 5, 4]，Alice 得分 3，Bob 得分 0，差值 3。
• Bob 取左侧 2，剩下 [5, 4]，Bob 得分 2，差值 1。
• Alice 取右侧 4，剩下 [5]，Alice 得分 4，差值 5。
• Bob 取最后一堆 5，Bob 得分 5，差值 0。
  最终 Alice 得分 7，Bob 得分 7，差值 0？——等一下，这样不对，我们需要用动态规划直接计算最优策略下的差值。

实际上，用 DP 计算的结果是 6，表示 Alice 可以在最优策略下比 Bob 多得 6 分。

思路分析

这是一个零和博弈，可以用区间动态规划求解。设石子的价值数组为 a[0..n-1]。

关键观察

如果定义 dp[l][r] 为当石子剩下下标区间 [l, r] 时，当前行动玩家能获得的最大得分差值（当前玩家得分 − 对方得分），那么：

• 如果当前玩家取走 a[l]，则剩下区间 [l+1, r]，对方在剩下区间成为“当前玩家”，对方能获得的最大差值（对方得分 − 当前玩家得分）为 dp[l+1][r]。
  那么当前玩家取左端的净差值 = a[l] − dp[l+1][r]。
• 同理，取右端 a[r] 的净差值 = a[r] − dp[l][r-1]。
• 当前玩家会选择两者中较大的一个。

因此状态转移方程为：

dp[l][r] = max(a[l] − dp[l+1][r], a[r] − dp[l][r-1])

解释：当前玩家先得到 a[l] 分，之后对方在 [l+1, r] 上获得差值（对方得分 − 当前玩家得分）为 dp[l+1][r]，所以当前玩家的净差值 = 得到 a[l] − 对方在后续的净差值。右端同理。

初始化

当 l == r 时，只有一堆石子，当前玩家必须取走，没有后续游戏，所以：

dp[l][l] = a[l]

最终答案

整个游戏是 Alice 先手面对区间 [0, n-1]，所以答案 = dp[0][n-1]。

逐步计算例子

以 stones = [3, 2, 5, 4] 为例，n = 4。

数组下标 0 到 3，值：[3, 2, 5, 4]。

步骤 1：初始化对角线

dp[l][l] = a[l]

dp[0][0] = 3
dp[1][1] = 2
dp[2][2] = 5
dp[3][3] = 4

步骤 2：区间长度为 2

• l=0, r=1：
  dp[0][1] = max(a[0] − dp[1][1], a[1] − dp[0][0])
  = max(3 − 2, 2 − 3) = max(1, −1) = 1

• l=1, r=2：
  dp[1][2] = max(a[1] − dp[2][2], a[2] − dp[1][1])
  = max(2 − 5, 5 − 2) = max(−3, 3) = 3

• l=2, r=3：
  dp[2][3] = max(a[2] − dp[3][3], a[3] − dp[2][2])
  = max(5 − 4, 4 − 5) = max(1, −1) = 1

步骤 3：区间长度为 3

• l=0, r=2：
  dp[0][2] = max(a[0] − dp[1][2], a[2] − dp[0][1])
  = max(3 − 3, 5 − 1) = max(0, 4) = 4

• l=1, r=3：
  dp[1][3] = max(a[1] − dp[2][3], a[3] − dp[1][2])
  = max(2 − 1, 4 − 3) = max(1, 1) = 1

步骤 4：区间长度为 4

• l=0, r=3：
  dp[0][3] = max(a[0] − dp[1][3], a[3] − dp[0][2])
  = max(3 − 1, 4 − 4) = max(2, 0) = 2

最终答案 = dp[0][3] = 2？
等等，我们之前示例输出是 6，这里计算是 2，说明题目可能有不同的规则。让我核对。

仔细看题目描述，这是“石子游戏 VIII”，我意识到我描述的是“石子游戏 I”（取两端得分的零和博弈），而实际石子游戏 VIII 是另一种规则。
我重新给出正确的石子游戏 VIII 题目（避免重复上面做过的博弈取石子两端题）：

正确题目：石子游戏 VIII（取走前缀石子堆，获得前缀和的博弈）

题目描述：
有 n 堆石子排成一行，每堆石子价值为 stones[i]（可能为负）。
定义前缀和 prefix[i] = stones[0] + stones[1] + ... + stones[i]，并设 prefix[-1] = 0。
游戏规则：

1. 玩家可以选择一个下标 i（i ≥ 1 且 i < n），取走前 i+1 堆石子（下标 0 到 i），获得分数 = prefix[i]，然后将剩下的石子堆重新编号（原 i+1 堆变成新 0 堆，原 i+2 堆变成新 1 堆，等等）。
2. 之后轮到对方，对方也从新的石子序列中选择一个 i ≥ 1 取走前缀，获得 新 prefix[i]。
3. 游戏直到只剩一堆石子时结束（此时不能操作）。
4. Alice 先手，Bob 后手，两人都绝顶聪明，Alice 希望最大化自己得分与 Bob 得分的差值。

问题：返回 Alice 能获得的最大得分差值。

思路分析

关键转换

第一次操作时，Alice 选择一个 i，得到 prefix[i] 分，之后游戏变成在 stones[i+1:] 上 Bob 先手。
设 dp[x] 表示当游戏从下标 x 开始（即石子为 stones[x..n-1]），当前先手玩家能获得的最大得分差值。

若当前先手玩家选择取到下标 j（j ∈ [x, n-2]，因为至少留一堆给后面），得到分数 = prefix[j]（注意：这里的 prefix 是原始数组前缀和，下标从 0 算）。
取走后，剩下石子从 j+1 开始，对方在剩下的游戏里为先手，对方能获得的最大差值 = dp[j+1]。
那么当前玩家在本次选择中，总差值 = 本次得分 prefix[j] − 对方后续的差值 dp[j+1]。

所以：

dp[x] = max_{j = x .. n-2} ( prefix[j] - dp[j+1] )

其中 dp[n-1] = 0，因为只剩一堆时不能操作，得分差为 0。

最终答案

游戏从下标 0 开始，Alice 先手，所以答案是 dp[0]。

举例计算

例子：stones = [-1, 2, -3, 4, -5]，n = 5

1. 前缀和：
   prefix[0] = -1
prefix[1] = 1
prefix[2] = -2
prefix[3] = 2
prefix[4] = -3

2. 从后往前计算 dp：

• dp[4] = 0（只剩 stones[4]，不能选）
• 计算 dp[3]：可选的 j = 3（取到 prefix[3]=2），剩下从 4 开始，对方 dp[4]=0。
  差值 = 2 − 0 = 2。
  所以 dp[3] = 2
• 计算 dp[2]：可选的 j = 2 或 3
  • j=2: 得分 prefix[2]=-2，剩下 dp[3]=2 → 差值 = -2 − 2 = -4
  • j=3: 得分 prefix[3]=2，剩下 dp[4]=0 → 差值 = 2 − 0 = 2
    取 max = 2
    所以 dp[2] = 2
• 计算 dp[1]：j = 1,2,3
  • j=1: 得分 1，剩下 dp[2]=2 → 差值 = 1 − 2 = -1
  • j=2: 得分 -2，剩下 dp[3]=2 → 差值 = -2 − 2 = -4
  • j=3: 得分 2，剩下 dp[4]=0 → 差值 = 2 − 0 = 2
    max = 2
    dp[1] = 2
• 计算 dp[0]：j = 0,1,2,3
  • j=0: 得分 -1，剩下 dp[1]=2 → 差值 = -1 − 2 = -3
  • j=1: 得分 1，剩下 dp[2]=2 → 差值 = 1 − 2 = -1
  • j=2: 得分 -2，剩下 dp[3]=2 → 差值 = -2 − 2 = -4
  • j=3: 得分 2，剩下 dp[4]=0 → 差值 = 2 − 0 = 2
    max = 2
    最终 dp[0] = 2

答案 = 2

复杂度

• 时间复杂度：O(n²)（朴素计算每个 dp[x] 需要枚举 j），但可以用后缀最大值优化到 O(n)。
• 空间复杂度：O(n)。

代码框架（Python）

def stoneGameVIII(stones):
    n = len(stones)
    prefix = [0] * n
    prefix[0] = stones[0]
    for i in range(1, n):
        prefix[i] = prefix[i-1] + stones[i]
    
    dp = [0] * n
    dp[n-1] = 0
    # 后缀最大值优化
    suffix_max = prefix[n-2] - dp[n-1]  # 当 x = n-2
    dp[n-2] = suffix_max
    for x in range(n-3, -1, -1):
        suffix_max = max(suffix_max, prefix[x] - dp[x+1])
        dp[x] = suffix_max
    return dp[0]

总结

石子游戏 VIII 是一个前缀和 + 从后向前 DP 的博弈问题，关键在于定义 dp[x] 为从位置 x 开始先手的最大差值，然后利用 dp[x] = max(prefix[j] − dp[j+1]) 进行转移，并可以用后缀最大值优化到线性时间。