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

题目描述

Alice 和 Bob 轮流取石子，规则如下：

• 有一排石子，每个石子有一个正整数权重，存储在数组 stones 中，长度为 n。
• 玩家可以从当前剩余石子序列的最左边或最右边取走一个石子，并获得该石子的权重分数。
• 当石子取完后，游戏结束。
• 假设 Alice 先手，Bob 后手，两人都采取最优策略，且都希望自己获得的总分数尽可能高于对方（即最大化自己的得分减去对方得分的差值）。
• 给定 stones，问 Alice 是否能赢得比赛（即 Alice 的得分 > Bob 的得分）？
  若返回 true，否则返回 false。

示例
输入：stones = [5,3,4,5]
输出：true
解释：

• Alice 先手可以取最左边的 5（得分 5），剩余 [3,4,5]。
• Bob 可以取最左边的 3（得分 3）或最右边的 5（得分 5）。假设 Bob 取最右边的 5（得分 5），剩余 [3,4]。
• Alice 取最左边的 3（得分 3，累计 8），剩余 [4]。
• Bob 取最后的 4（得分 4，累计 9）。
  最终 Alice 得分 8，Bob 得分 9，Alice 输了？等等，这个例子似乎 Alice 没赢。但原题示例的输出是 true，我们需要更仔细地分析最优策略。

实际上，这个题目是一个经典的零和博弈，可以用区间 DP 计算先手在任意子区间 [i, j] 能获得的最大净胜分（先手得分 - 后手得分）。

问题分析
设 dp[i][j] 表示当石子只剩下子数组 stones[i...j] 时，当前先手玩家（不一定是 Alice）在这个子区间能获得的最大净胜分（即自己的得分减去对方得分的差值）。

我们要求的是 dp[0][n-1] 是否大于 0。若大于 0，表示先手（Alice）在全局能获得比后手更高的分数。

状态转移方程推导

当前先手玩家面对区间 [i, j]，他有两种选择：

1. 取 stones[i]（左端石子）：
   他立刻获得 stones[i] 的分数，然后轮到对方在区间 [i+1, j] 作为先手。
   此时对方在 [i+1, j] 会得到净胜分 dp[i+1][j]（相对于对方自己而言）。
   那么对于当前玩家来说，在取走 stones[i] 之后，整个游戏的净胜分（当前玩家得分减去对方得分）为：

   stones[i] - dp[i+1][j]
   

   解释：dp[i+1][j] 是对方在新区间作为先手的净胜分（对方得分 - 我方得分）。
   所以当前玩家的净胜分 = stones[i] - (对方得分 - 我方在剩余局面的得分)
   但更直接的理解：dp[i+1][j] 是对方在剩余区间能比当前玩家多得的分（对方净胜），所以当前玩家在取左端的净胜 = stones[i] - dp[i+1][j]。

2. 取 stones[j]（右端石子）：
   同理，净胜分为：

   stones[j] - dp[i][j-1]
   

因为是最优策略，当前先手会选择两者中较大的那个：

\[dp[i][j] = \max(stones[i] - dp[i+1][j],\; stones[j] - dp[i][j-1]) \]

边界条件
当区间长度为 1（即 i == j）时，当前先手只能取这一个石子，净胜分就是 stones[i]：

\[dp[i][i] = stones[i] \]

计算顺序
因为 dp[i][j] 依赖于 dp[i+1][j] 和 dp[i][j-1]，即更短的区间，所以我们可以按区间长度 len 从 1 到 n 进行递推。

示例详细推导
stones = [5,3,4,5]，n=4。

1. 初始化 len=1：
   dp[0][0]=5, dp[1][1]=3, dp[2][2]=4, dp[3][3]=5。

2. len=2：

   • i=0,j=1：dp[0][1] = max(5 - dp[1][1], 3 - dp[0][0]) = max(5-3, 3-5) = max(2, -2) = 2。
   • i=1,j=2：dp[1][2] = max(3 - dp[2][2], 4 - dp[1][1]) = max(3-4, 4-3) = max(-1, 1) = 1。
   • i=2,j=3：dp[2][3] = max(4 - dp[3][3], 5 - dp[2][2]) = max(4-5, 5-4) = max(-1, 1) = 1。

3. len=3：

   • i=0,j=2：dp[0][2] = max(5 - dp[1][2], 4 - dp[0][1]) = max(5-1, 4-2) = max(4, 2) = 4。
   • i=1,j=3：dp[1][3] = max(3 - dp[2][3], 5 - dp[1][2]) = max(3-1, 5-1) = max(2, 4) = 4。

4. len=4：

   • i=0,j=3：dp[0][3] = max(5 - dp[1][3], 5 - dp[0][2]) = max(5-4, 5-4) = max(1, 1) = 1。

最终 dp[0][3] = 1 > 0，所以 Alice（先手）能赢，输出 true。

为什么示例中 Alice 能赢？
上面的最优策略路径：

• Alice 先手取左端 5（stones[0]），剩余 [3,4,5]。此时 Bob 在 [1,3] 作为先手，dp[1][3]=4，表示 Bob 能比 Alice 在剩余局面多得 4 分。
• 即：Alice 在第一步后总分 = 5，Bob 在剩余局面对抗 Alice 能净胜 4 分（Bob得分 - Alice在剩余得分 = 4）。
  但 Alice 总净胜 = 5（第一步得分） - 4（Bob 净胜） = 1，符合 dp[0][3]=1。

具体对局：

1. Alice 取 5，剩 [3,4,5]。
2. Bob 取 3（左端）或 5（右端），他会选择最优。若 Bob 取 5（右端），剩余 [3,4]，此时 Alice 在 [3,4] 作为先手净胜分 dp[1][2]=1（即 Alice 能比 Bob 多得 1 分）。
   最终 Alice 总得分 5 + 4 = 9，Bob 总得分 5 + 3 = 8，Alice 赢。

时间复杂度与空间复杂度

• 时间复杂度：O(n²)，需要填满 n×n 的 DP 表。
• 空间复杂度：O(n²)，可优化为 O(n)（只保留上一行），但实现时用二维数组更直观。

最终代码逻辑（Python 风格伪代码）

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