石子游戏 VIII（博弈类区间DP）

题目描述
Alice 和 Bob 在玩一个石子游戏，游戏规则如下：

• 有 n 堆石子排成一行，每堆石子有正整数的价值。
• 游戏开始时，Alice 先手，Bob 后手。
• 玩家轮流从最左边非空的石子堆中取出若干石子（至少取 1 个，至多取完该堆），但不能直接取最左边的第一堆。
• 当某玩家取完一堆石子后，如果该堆石子是第 i 堆（i > 1），则系统会自动将第 1 堆到第 i-1 堆的石子全部移除。
• 游戏结束时，每个玩家的得分为其取出石子的总价值。
• 双方都采取最优策略，目标是最大化自己的得分。

给定石子堆数组 stones，请返回 Alice 能获得的最大得分。

解题思路
这个问题是典型的区间动态规划结合博弈论。我们需要从右向左分析，因为每次操作会影响左侧的所有堆。

步骤详解

步骤1：理解游戏规则

• 不能直接取第一堆，必须从第二堆或更右边开始取
• 取第 i 堆后，第 1 到 i-1 堆会被自动移除
• 这意味着取第 i 堆时，玩家能立即获得 stones[i] 的分数，并且游戏会从第 i+1 堆重新开始

步骤2：定义状态
定义 dp[i] 表示当游戏从第 i 堆开始时（即第 1 到 i-1 堆已被移除），当前玩家能获得的最大净胜分（当前玩家得分 - 对手得分）。

步骤3：状态转移方程
对于位置 i（从 0 开始索引），当前玩家有两种选择：

1. 取第 i 堆：获得 stones[i] 分，游戏跳到 i+1
2. 不取第 i 堆，考虑取更右边的堆

状态转移方程：
dp[i] = max(stones[i] - dp[i+1], dp[i+1])

解释：

• stones[i] - dp[i+1]：取第 i 堆，得到 stones[i] 分，但对手在剩下的游戏中会有 dp[i+1] 的优势
• dp[i+1]：不取第 i 堆，考虑右边的选择

步骤4：边界条件
当 i = n-1（最后一堆）时：
dp[n-1] = stones[n-1]（只能取这堆）

步骤5：计算顺序
从右向左计算：

• 初始化 dp[n-1] = stones[n-1]
• 对于 i 从 n-2 到 1：dp[i] = max(stones[i] - dp[i+1], dp[i+1])

步骤6：最终答案
由于 Alice 先手，且不能直接取第一堆，游戏从第 1 堆开始考虑：
answer = dp[1]

举例说明

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

• n = 5
• 计算 dp 数组：
  • dp[4] = stones[4] = -5
  • dp[3] = max(4 - (-5), -5) = max(9, -5) = 9
  • dp[2] = max(-3 - 9, 9) = max(-12, 9) = 9
  • dp[1] = max(2 - 9, 9) = max(-7, 9) = 9
• 答案：dp[1] = 9

例2：stones = [1,2,3,4,5]

• n = 5
• 计算 dp 数组：
  • dp[4] = 5
  • dp[3] = max(4 - 5, 5) = max(-1, 5) = 5
  • dp[2] = max(3 - 5, 5) = max(-2, 5) = 5
  • dp[1] = max(2 - 5, 5) = max(-3, 5) = 5
• 答案：dp[1] = 5

算法实现

def stoneGameVIII(stones):
    n = len(stones)
    dp = [0] * n
    dp[n-1] = stones[n-1]
    
    for i in range(n-2, 0, -1):
        dp[i] = max(stones[i] - dp[i+1], dp[i+1])
    
    return dp[1]

复杂度分析

• 时间复杂度：O(n)，只需要遍历数组一次
• 空间复杂度：O(n)，用于存储 dp 数组

这个解法巧妙地利用了动态规划来模拟博弈过程，通过净胜分的概念将复杂的博弈问题转化为简单的动态规划问题。