石子游戏 VII

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

有一个数组 stones，表示一排石子的价值，其中 stones[i] 表示第 i 堆石子的价值。Alice 和 Bob 轮流进行游戏，Alice 先手。在每一轮中，玩家可以执行以下操作之一：

1. 移除当前最左边的一堆石子，并得到剩余石子价值之和的分数。
2. 移除当前最右边的一堆石子，并得到剩余石子价值之和的分数。

当没有石子剩下时，游戏结束。两位玩家都希望最大化自己的总得分。假设两人都发挥最佳水平，求 Alice 能够领先 Bob 的分数（即 Alice 的得分减去 Bob 的得分）。如果 Alice 无法获胜，则返回负数表示 Bob 的领先分数。

解题思路

1. 问题分析

游戏的关键是：

• 每次移除一堆石子（左边或右边），得到的分数是移除后剩余石子的总价值。
• 剩余石子价值之和可以用前缀和快速计算。
• 这是一个零和博弈，即 Alice 的得分减去 Bob 的得分就是最终结果，Bob 会尽量最小化这个差值。

定义：

• 用 sum[i][j] 表示石子堆 i 到 j 的总价值（可通过前缀和快速计算）。
• 用 dp[i][j] 表示当石子堆剩下 [i, j] 区间时，当前玩家（无论是 Alice 还是 Bob）能够取得的最大领先分数（即当前玩家得分减去对手得分的差值）。

2. 状态转移

考虑区间 [i, j]：

• 如果当前玩家移除左边石子堆 i，则得到的分数是 sum[i+1][j]（移除后剩下的石子总价值）。
  之后轮到对手在区间 [i+1, j] 上操作，对手能取得的最大领先分数是 dp[i+1][j]（这是对手相对于当前玩家的差值）。
  因此，当前玩家选择移除左边的领先分数是：

  left = sum[i+1][j] - dp[i+1][j]
  

  解释：当前玩家得到 sum[i+1][j] 分，而对手在剩下的游戏中能领先 dp[i+1][j] 分（对手领先表示当前玩家落后这么多），所以当前玩家的净领先是 得分 - 对手的领先。

• 同理，如果移除右边石子堆 j，得到的分数是 sum[i][j-1]，对手在 [i, j-1] 上操作，对手领先分数是 dp[i][j-1]。
  所以右边选择带来的领先分数是：

  right = sum[i][j-1] - dp[i][j-1]
  

• 当前玩家会选择能让自己领先分数最大化的操作：

  dp[i][j] = max(left, right)
  

3. 边界条件

当区间只有一个石子堆时（i == j），移除后没有石子剩下，剩余石子价值之和为 0，所以得分为 0。
因此：

dp[i][i] = 0

4. 计算顺序

区间 DP 通常按区间长度从小到大计算。

• 先计算所有长度为 1 的区间（dp[i][i] = 0）。
• 然后计算长度 2, 3, ..., n 的区间。

5. 答案

最终 dp[0][n-1] 表示在初始区间 [0, n-1] 上，先手玩家（Alice）能领先的分数。

举例说明

假设 stones = [5, 3, 1, 4]。
计算前缀和 prefix 以便快速求区间和：
prefix[0] = 0
prefix[1] = 5
prefix[2] = 8
prefix[3] = 9
prefix[4] = 13

区间和 sum[i][j] = prefix[j+1] - prefix[i]。

计算过程：

1. 初始化 dp[i][i] = 0。

2. 区间长度 2：

   • [0,1]：

     • 移除左边 0：得分 = sum[1][1] = prefix[2]-prefix[1] = 8-5=3，dp[1][1]=0，left = 3 - 0 = 3。
     • 移除右边 1：得分 = sum[0][0] = prefix[1]-prefix[0] = 5-0=5，dp[0][0]=0，right = 5 - 0 = 5。
     • 选最大：dp[0][1] = max(3,5) = 5。

   • [1,2]：

     • 移除左边 1：得分 = sum[2][2] = prefix[3]-prefix[2] = 9-8=1，dp[2][2]=0，left=1。
     • 移除右边 2：得分 = sum[1][1] = 8-5=3，dp[1][1]=0，right=3。
     • dp[1][2] = max(1,3) = 3。

   • [2,3]：

     • 移除左边 2：得分 = sum[3][3] = prefix[4]-prefix[3] = 13-9=4，dp[3][3]=0，left=4。
     • 移除右边 3：得分 = sum[2][2] = 9-8=1，dp[2][2]=0，right=1。
     • dp[2][3] = max(4,1) = 4。

3. 区间长度 3：

   • [0,2]：

     • 移除左边 0：得分 = sum[1][2] = prefix[3]-prefix[1] = 9-5=4，dp[1][2]=3，left=4-3=1。
     • 移除右边 2：得分 = sum[0][1] = prefix[2]-prefix[0] = 8-0=8，dp[0][1]=5，right=8-5=3。
     • dp[0][2] = max(1,3) = 3。

   • [1,3]：

     • 移除左边 1：得分 = sum[2][3] = prefix[4]-prefix[2] = 13-8=5，dp[2][3]=4，left=5-4=1。
     • 移除右边 3：得分 = sum[1][2] = prefix[3]-prefix[1] = 9-5=4，dp[1][2]=3，right=4-3=1。
     • dp[1][3] = max(1,1) = 1。

4. 区间长度 4：[0,3]

   • 移除左边 0：得分 = sum[1][3] = prefix[4]-prefix[1] = 13-5=8，dp[1][3]=1，left=8-1=7。
   • 移除右边 3：得分 = sum[0][2] = prefix[3]-prefix[0] = 9-0=9，dp[0][2]=3，right=9-3=6。
   • dp[0][3] = max(7,6) = 7。

最终结果：dp[0][3] = 7，表示 Alice 能领先 7 分。

代码框架（Python风格）

def stoneGameVII(stones):
    n = len(stones)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + stones[i]
    
    def sum_range(i, j):
        return prefix[j+1] - prefix[i]
    
    dp = [[0] * n for _ in range(n)]
    
    for length in range(2, n+1):
        for i in range(n - length + 1):
            j = i + length - 1
            left = sum_range(i+1, j) - dp[i+1][j]
            right = sum_range(i, j-1) - dp[i][j-1]
            dp[i][j] = max(left, right)
    
    return dp[0][n-1]

复杂度分析

• 时间复杂度：O(n²)，因为要计算所有 O(n²) 个区间，每个区间转移是 O(1)。
• 空间复杂度：O(n²)，用于存储 dp 表。

关键点

1. 定义 dp[i][j] 为当前玩家在区间 [i, j] 上能获得的最大领先分数（当前玩家得分减去对手得分）。
2. 状态转移时，当前玩家选择左端或右端移除石子，得到的领先分数是：本次得分减去对手在剩余区间上的领先分数。
3. 利用前缀和快速计算区间和。
4. 最终 dp[0][n-1] 即为 Alice 的领先分数。