石子游戏 VII（博弈类区间DP的典型题目）

题目描述
石子游戏 VII 是一个典型的博弈类区间动态规划问题。问题描述如下：

有一行排成一列的石子堆，用数组 stones 表示，stones[i] 表示第 i 堆石子的价值。Alice 和 Bob 轮流进行游戏，Alice 先手。在每一轮中，当前玩家可以从这行石子的最左端或者最右端移除一堆石子，并获得剩余石子价值总和的得分。游戏持续到没有石子剩下为止。两名玩家都采用最优策略，目标是最大化自己的总得分。假设两名玩家的得分差定义为 (Alice 的得分 - Bob 的得分)，请返回 Alice 在最优策略下能够获得的最大得分差。

例如，stones = [5,3,1,4,2]，游戏过程可能如下：

• Alice 移除最左端 5，获得剩余石子总和 3+1+4+2=10 分，剩下 [3,1,4,2]。
• Bob 移除最左端 3，获得剩余总和 1+4+2=7 分，剩下 [1,4,2]。
• Alice 移除最右端 2，获得剩余总和 1+4=5 分，剩下 [1,4]。
• Bob 移除最左端 1，获得剩余总和 4 分，剩下 [4]。
• Alice 移除最后的 4，获得剩余总和 0 分。
  最终 Alice 总得分 10+5+0=15，Bob 总得分 7+4=11，得分差为 4。但这不是最优策略，需要计算在双方都最优下的最大得分差。

解题步骤

步骤1：理解游戏与得分计算
每次移除一堆石子，得到的得分是移除后剩下石子的价值总和。因此，在区间 [l, r] 上，如果当前玩家移除左端 stones[l]，则得分为 sum[l+1, r]（即区间 [l+1, r] 的和）；如果移除右端 stones[r]，则得分为 sum[l, r-1]。之后轮到对方在缩小的区间上操作。

由于双方都最优，当前玩家在选择时，会考虑自己选择后，对方也会在剩下的区间上最优应对，从而影响最终自己的净得分（得分差）。

步骤2：定义状态
设 dp[l][r] 表示当石子堆剩下区间 [l, r] 时，当前先手玩家（不一定是 Alice）能够获得的最大得分差（即当前先手玩家得分减去对手得分的差值）。

注意：在整个游戏中，Alice 是先手，所以最终答案是 dp[0][n-1]，其中 n 是石子堆数量。

步骤3：状态转移方程
考虑区间 [l, r]：

1. 如果当前玩家移除左端石子 stones[l]，则他立即得到 sum[l+1, r] 分。之后轮到对方在区间 [l+1, r] 上先手，对方能获得的最大得分差是 dp[l+1][r]（对方得分减去当前玩家后续得分的差值）。那么，在当前玩家看来，这次选择带来的净得分差是：
   score_left = sum[l+1, r] - dp[l+1][r]
   解释：当前玩家得到 sum[l+1, r] 分，但接下来对方在子区间上先手，对方会拉开 dp[l+1][r] 的分差（对方得分减去当前玩家后续得分），所以当前玩家的净得分差就是 sum[l+1, r] - dp[l+1][r]。

2. 同理，如果移除右端石子 stones[r]，则净得分差为：
   score_right = sum[l, r-1] - dp[l][r-1]

当前玩家会选择使自己净得分差最大的一种操作：
dp[l][r] = max(score_left, score_right)

步骤4：边界条件
当区间长度为 1 时，即 l == r，移除最后一个石子后无剩余石子，得分为 0，且无后续游戏，所以 dp[l][r] = 0。

步骤5：计算顺序与预处理
由于 dp[l][r] 依赖 dp[l+1][r] 和 dp[l][r-1]，即需要先知道更小区间的结果，所以计算顺序应为区间长度 len 从 2 到 n 递增（len=1 时已初始化）。

另外，我们需要快速计算任意区间和 sum[l, r]，可以预处理前缀和数组 prefix，其中 prefix[i] 表示前 i 个元素的和（prefix[0]=0），则 sum[l, r] = prefix[r+1] - prefix[l]。

步骤6：具体例子演示
以 stones = [5,3,1,4,2] 为例，n=5，计算过程如下：

预处理前缀和：
下标: 0 1 2 3 4
数组: 5 3 1 4 2
前缀和: prefix[0]=0, prefix[1]=5, prefix[2]=8, prefix[3]=9, prefix[4]=13, prefix[5]=15。

初始化：所有 dp[l][l]=0。

区间长度 len=2：

• [0,1]: sum[1,1]=prefix[2]-prefix[1]=8-5=3, sum[0,0]=prefix[1]-prefix[0]=5-0=5
  score_left = 3 - dp[1][1] = 3 - 0 = 3
  score_right = 5 - dp[0][0] = 5 - 0 = 5
  dp[0][1] = max(3,5) = 5
• [1,2]: sum[2,2]=1, sum[1,1]=3
  score_left = 1 - 0 = 1, score_right = 3 - 0 = 3 → dp[1][2]=3
• [2,3]: sum[3,3]=4, sum[2,2]=1 → 4 和 1 → dp[2][3]=4
• [3,4]: sum[4,4]=2, sum[3,3]=4 → 2 和 4 → dp[3][4]=4

区间长度 len=3：

• [0,2]: sum[1,2]=prefix[3]-prefix[1]=9-5=4, sum[0,1]=prefix[2]-prefix[0]=8-0=8
  score_left = 4 - dp[1][2] = 4 - 3 = 1
  score_right = 8 - dp[0][1] = 8 - 5 = 3
  dp[0][2] = max(1,3) = 3
• [1,3]: sum[2,3]=prefix[4]-prefix[2]=13-8=5, sum[1,2]=prefix[3]-prefix[1]=9-5=4
  score_left = 5 - dp[2][3] = 5 - 4 = 1
  score_right = 4 - dp[1][2] = 4 - 3 = 1
  dp[1][3] = 1
• [2,4]: sum[3,4]=prefix[5]-prefix[3]=15-9=6, sum[2,3]=prefix[4]-prefix[2]=13-8=5
  score_left = 6 - dp[3][4] = 6 - 4 = 2
  score_right = 5 - dp[2][3] = 5 - 4 = 1
  dp[2][4] = 2

区间长度 len=4：

• [0,3]: sum[1,3]=prefix[4]-prefix[1]=13-5=8, sum[0,2]=prefix[3]-prefix[0]=9-0=9
  score_left = 8 - dp[1][3] = 8 - 1 = 7
  score_right = 9 - dp[0][2] = 9 - 3 = 6
  dp[0][3] = 7
• [1,4]: sum[2,4]=prefix[5]-prefix[2]=15-8=7, sum[1,3]=prefix[4]-prefix[1]=13-5=8
  score_left = 7 - dp[2][4] = 7 - 2 = 5
  score_right = 8 - dp[1][3] = 8 - 1 = 7
  dp[1][4] = 7

区间长度 len=5：

• [0,4]: sum[1,4]=prefix[5]-prefix[1]=15-5=10, sum[0,3]=prefix[4]-prefix[0]=13-0=13
  score_left = 10 - dp[1][4] = 10 - 7 = 3
  score_right = 13 - dp[0][3] = 13 - 7 = 6
  dp[0][4] = max(3,6) = 6

最终结果 dp[0][4] = 6，表示 Alice 在先手情况下，采用最优策略可以获得的最大得分差为 6。

步骤7：算法复杂度

• 时间复杂度：O(n²)，因为需要计算 O(n²) 个状态，每个状态转移是 O(1)。
• 空间复杂度：O(n²)，用于存储 dp 表。可以优化到 O(n) 因为每个状态只依赖相邻行，但通常实现用二维数组更清晰。

步骤8：代码实现（Python风格）

def stoneGameVII(stones):
    n = len(stones)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + stones[i]
    
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n+1):
        for l in range(0, n-length+1):
            r = l + length - 1
            # 移除左端
            sum_left = prefix[r+1] - prefix[l+1]  # sum[l+1, r]
            score_left = sum_left - dp[l+1][r]
            # 移除右端
            sum_right = prefix[r] - prefix[l]     # sum[l, r-1]
            score_right = sum_right - dp[l][r-1]
            dp[l][r] = max(score_left, score_right)
    
    return dp[0][n-1]

总结
石子游戏 VII 是区间动态规划在博弈问题中的经典应用。关键在于定义状态为当前先手玩家在区间上的最大得分差，并通过考虑自己选择后对方最优应对来构造转移。通过预处理前缀和优化区间和计算，即可高效求解。