区间动态规划例题：石子游戏 III

题目描述

石子游戏 III 是石子游戏系列的一个经典扩展。问题如下：
一排 n 堆石子排成一行，第 i 堆石子有 stones[i] 个（stones[i] 可为负数，表示玩家可能会输分）。两名玩家 Alice 和 Bob 轮流进行游戏，Alice 先手。在每个玩家的回合中，可以从当前剩余石子堆的最前面取走 1 堆、2 堆 或 3 堆石子，并将这些被取走的石子堆的总和加到自己的得分中。当没有石子堆剩下时，游戏结束。
假设两名玩家都发挥出最佳水平，问 Alice 是否能赢得比赛？
如果 Alice 的得分严格大于 Bob 的得分，则 Alice 赢；如果相等，则视为 Alice 输。
题目要求返回 "Alice" 或 "Bob" 表示胜者。

示例 1

输入：stones = [1,2,3,7]
输出："Bob"
解释：
Alice 可以取前 1、2 或 3 堆石子。  
如果 Alice 取 1 堆（得 1 分），剩下 [2,3,7] 给 Bob，Bob 可以取 2 堆（得 5 分）或 3 堆（得 12 分），Bob 总会赢。  
如果 Alice 取 2 堆（得 3 分），剩下 [3,7] 给 Bob，Bob 取 2 堆得 10 分，Bob 赢。  
如果 Alice 取 3 堆（得 6 分），剩下 [7] 给 Bob，Bob 取 1 堆得 7 分，Bob 赢。  
所以 Alice 无法赢，返回 "Bob"。

示例 2

输入：stones = [1,2,3,-9]
输出："Alice"
解释：
Alice 取 3 堆得 6 分，剩下 [-9] 给 Bob，Bob 得 -9 分，Alice 总分 6 > -9，Alice 赢。

解题思路

这是一个零和博弈问题，可以使用区间动态规划来求解。
定义 dp[i] 表示：当剩下石子堆为从第 i 堆到最后一堆时，当前玩家能获得的相对最大净胜分（即当前玩家得分减去对手得分的最大值）。

• 如果当前是 Alice 的回合，dp[i] 就是 Alice 在这个剩余局面下的（Alice得分 - Bob得分）的最大值。
• 转移时，当前玩家可以选择取 1、2 或 3 堆，取完后局面交给对手，对手也会最优应对，所以当前玩家在取走石子后的净胜分是：

  取走的石子总和 - 对手在剩下局面下的净胜分
  

  因为对手的净胜分（从对手角度）就是 dp[i + k]（k 是取走的堆数），但从当前玩家角度看，对手的净胜分会减少当前玩家的净胜分，所以是减法。

状态转移方程：
设 prefixSum[i] 是前 i 堆石子的前缀和（方便计算区间和），suffixSum[i] 可从后往前计算，但我们直接计算区间和：

sum(i, j) = stones[i] + stones[i+1] + ... + stones[j]

则：

dp[i] = max(
    sum(i, i)   - dp[i+1],          // 取 1 堆
    sum(i, i+1) - dp[i+2],          // 取 2 堆
    sum(i, i+2) - dp[i+3]           // 取 3 堆
)

其中，dp[n] = 0 表示没有石子时净胜分为 0。

最终，如果 dp[0] > 0，则 Alice 净胜分为正，Alice 赢；否则 Bob 赢。

逐步详解

步骤 1：定义状态

• 设 n = len(stones)。
• 定义 dp[i]：当石子堆从下标 i 到 n-1 时，当前玩家能获得的最大净胜分（当前玩家得分减去对手得分）。
• 初始化 dp[n] = 0（没有石子时净胜分为 0）。

步骤 2：前缀和优化

为了快速计算 sum(i, j)，我们使用前缀和数组 prefix：

prefix[0] = 0
prefix[k] = stones[0] + ... + stones[k-1]  (k 从 1 到 n)

那么：

sum(i, j) = prefix[j+1] - prefix[i]

注意：i, j 是原始下标（从 0 开始）。

步骤 3：状态转移

从后往前计算 dp[i]，因为 dp[i] 依赖于 dp[i+1]、dp[i+2]、dp[i+3]。
对于每个 i，枚举取走的堆数 k = 1, 2, 3：

if i + k - 1 < n:
    score = (prefix[i+k] - prefix[i]) - dp[i+k]
    dp[i] = max(dp[i], score)

这里 score 表示：当前玩家取走这 k 堆得到分数 prefix[i+k]-prefix[i]，然后对手在 i+k 之后的最优净胜分是 dp[i+k]，所以当前玩家净胜分为取走的分数减去对手的净胜分。

步骤 4：边界与结果

• 如果 dp[0] > 0，返回 "Alice"。
• 否则返回 "Bob"。

示例推导（stones = [1,2,3,7]）

n = 4, prefix = [0,1,3,6,13]

从后往前计算：

• dp[4] = 0
• i=3: 只能取 1 堆
  sum(3,3)=7，dp[3] = 7 - dp[4] = 7
• i=2: 可取 1 堆或 2 堆
  • 取 1 堆: sum(2,2)=3，3 - dp[3] = 3 - 7 = -4
  • 取 2 堆: sum(2,3)=10，10 - dp[4] = 10
dp[2] = max(-4, 10) = 10
• i=1: 可取 1、2、3 堆
  • 取 1 堆: sum(1,1)=2，2 - dp[2] = 2 - 10 = -8
  • 取 2 堆: sum(1,2)=5，5 - dp[3] = 5 - 7 = -2
  • 取 3 堆: sum(1,3)=12，12 - dp[4] = 12
dp[1] = max(-8, -2, 12) = 12
• i=0: 可取 1、2、3 堆
  • 取 1 堆: sum(0,0)=1，1 - dp[1] = 1 - 12 = -11
  • 取 2 堆: sum(0,1)=3，3 - dp[2] = 3 - 10 = -7
  • 取 3 堆: sum(0,2)=6，6 - dp[3] = 6 - 7 = -1
dp[0] = max(-11, -7, -1) = -1

dp[0] = -1 < 0，所以 Alice 会输，返回 "Bob"。

代码实现（Python）

def stoneGameIII(stones):
    n = len(stones)
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i+1] = prefix[i] + stones[i]
    
    dp = [float('-inf')] * (n + 1)
    dp[n] = 0
    
    for i in range(n-1, -1, -1):
        for k in range(1, 4):
            if i + k - 1 >= n:
                break
            score = (prefix[i+k] - prefix[i]) - dp[i+k]
            dp[i] = max(dp[i], score)
    
    if dp[0] > 0:
        return "Alice"
    elif dp[0] < 0:
        return "Bob"
    else:
        return "Tie"  # 但题目要求 Alice 严格大于 Bob 才赢，所以平局算 Alice 输

（注意：原题规定平局算 Alice 输，所以判断 dp[0] > 0 返回 "Alice"，否则 "Bob"。）

复杂度分析

• 时间复杂度：O(n)，因为每个状态最多枚举 3 种选择，n 是石子堆数。
• 空间复杂度：O(n) 用于 dp 数组和前缀和。

总结

这个题是石子游戏系列中较有挑战的一题，通过定义相对净胜分作为状态，从后向前递推，可以避免复杂的博弈分析，将问题转化为简单的极大极小值选择。
关键点：

1. 状态定义：dp[i] 是从 i 到末尾的当前玩家最大净胜分。
2. 转移方程：当前取走的分数减去对手在剩余局面的最优净胜分。
3. 前缀和加速区间和计算。