石子游戏 IX（博弈类区间DP，取石子问题的另一种变形）

题目描述：
有 n 堆石子排成一行，每堆石子有正整数个石子数 piles[i]。两名玩家轮流进行以下操作：从当前剩余石子的最左端或最右端取走一整堆石子，并获得这堆石子的数量作为得分。游戏持续到所有石子都被取完。最终，玩家得分高者获胜。假设两名玩家都采取最优策略，问先手玩家是否可以获胜？注意，这里与预测赢家问题的区别在于，本题允许 piles 中包含负数石子数（可以视为某种惩罚），但玩家仍然必须取走整堆石子（即得分可能为负）。不过，通常题目中石子数为正整数，但本题扩展版本中会包含负数的情况。但为了简化，我们这里考虑 piles 中的数字可能是任意整数（正、负、零），玩家目标是最大化自己的得分，而不是单纯比较最终得分是否更高。实际上，这是一个零和博弈，问先手玩家的最大可能净胜分（先手得分减后手得分）是否大于等于 0。

更形式化地：给定一个整数数组 piles，先手玩家从数组两端取数，每次取一个，两人都希望自己最终的总和尽可能大（即最大化自己的总得分）。如果先手玩家可以确保自己的总得分不低于后手玩家，则先手获胜。但更一般的问题是：假设两名玩家都发挥最佳，返回先手玩家能获得的最大净胜分（先手得分 - 后手得分）。

解题过程循序渐进讲解

这个问题是博弈动态规划的经典模型之一，通常称为“石子游戏”的变种，与“预测赢家”、“石子游戏 II”等同属一类，但这里的数组可包含负数。解决它的核心思路是区间DP，通过定义状态来表示在某个子区间上当前先手玩家能获得的最大净胜分。

步骤1：定义状态

我们定义 dp[i][j] 表示：当石子堆只剩下下标从 i 到 j 的子数组时（闭区间 [i, j]），当前要行动的玩家（注意：不一定是全局的先手，而是轮到谁）在这一轮能获得的最大净胜分。这里的“净胜分”指的是：当前玩家在这一轮及之后的所有轮次中，自己得到的总分数减去对手得到的总分数。

换句话说，在区间 [i, j] 上，当前玩家先行动，他最终能比对手多拿多少分（正值表示他最终会比对手多得这么多分，负值表示他会比对手少得这么多分）。

为什么这样定义是有效的？因为博弈的对称性：在每一步，当前玩家都会选择对自己最有利的操作，而对手也会在剩下的区间上采取最优策略。这个定义让我们能用较小的区间递推出较大区间的结果。

步骤2：状态转移

考虑当前区间 [i, j]，当前玩家有两种选择：

1. 取走 piles[i]（左端石子堆），那么他会立即得到 piles[i] 分，然后轮到对手在区间 [i+1, j] 上行动。在区间 [i+1, j] 上，对手作为当前玩家，他的最优净胜分是 dp[i+1][j]（即对手在剩下的游戏中能比当前玩家多得的分）。但注意，dp[i+1][j] 是从对手视角的净胜分，那么从当前玩家的视角，他取走 piles[i] 后，整个游戏的净胜分（当前玩家得分减对手得分）就是：

\[ \text{score}_L = piles[i] - dp[i+1][j] \]

解释：当前玩家得了 piles[i]，但在剩下的区间上对手能比他多得 dp[i+1][j] 分，所以当前玩家总的净胜分是 piles[i] 减去对手的净胜分。

2. 取走 piles[j]（右端石子堆），类似地，得到：

\[ \text{score}_R = piles[j] - dp[i][j-1] \]

当前玩家是理智的，他会选择对自己更有利的那一端，即：

\[dp[i][j] = \max(\text{score}_L, \text{score}_R) = \max(piles[i] - dp[i+1][j],\; piles[j] - dp[i][j-1]) \]

这就是核心的状态转移方程。

步骤3：边界条件

当区间长度为 1 时，即 i == j，当前玩家只有一堆可取，取走后游戏结束，没有后续区间。那么：

\[dp[i][i] = piles[i] \]

因为当前玩家取走这堆石子，得到 piles[i] 分，对手得 0 分，净胜分就是 piles[i]。

步骤4：递推顺序

由状态转移方程可知，计算 dp[i][j] 需要 dp[i+1][j] 和 dp[i][j-1]，即需要比当前区间更短的区间的结果。因此，我们可以按区间长度 len 从小到大递推：

• 初始化：len = 1 时，dp[i][i] = piles[i]。
• 对于 len 从 2 到 n：
  • 对于每个左端点 i，右端点 j = i + len - 1（保证 j < n）：
    • 计算 dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])。

这样，当 len = n 时，dp[0][n-1] 就表示在整个数组上，当前先手玩家（即全局先手）能获得的最大净胜分。

步骤5：判断结果

最终，如果 dp[0][n-1] >= 0，说明先手玩家能保证自己的总得分不低于后手玩家（即先手不败，或严格来说净胜分非负），先手可以获胜（或至少平局，如果题目要求严格大于则需 >0）。但通常我们返回 dp[0][n-1] 本身的值，或者返回布尔值表示先手是否不败。

步骤6：示例

假设 piles = [3, 9, 1, 2]。

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

2. len=2：

   • [0,1]: dp[0][1] = max(3 - dp[1][1], 9 - dp[0][0]) = max(3-9, 9-3) = max(-6, 6) = 6。
   • [1,2]: max(9-1, 1-9) = max(8, -8) = 8。
   • [2,3]: max(1-2, 2-1) = max(-1, 1) = 1。

3. len=3：

   • [0,2]: max(3 - dp[1][2], 1 - dp[0][1]) = max(3-8, 1-6) = max(-5, -5) = -5。
   • [1,3]: max(9 - dp[2][3], 2 - dp[1][2]) = max(9-1, 2-8) = max(8, -6) = 8。

4. len=4：

   • [0,3]: max(3 - dp[1][3], 2 - dp[0][2]) = max(3-8, 2-(-5)) = max(-5, 7) = 7。

最终 dp[0][3] = 7 > 0，所以先手可以获胜，且净胜 7 分。

我们可以验证一下最优玩法：先手取 2（右端），剩下 [3,9,1]；后手面临 [3,9,1]，若后手取 3，则先手在 [9,1] 上能得 9（取9），后手得1，总分先手=2+9=11，后手=3+1=4，净胜7；若后手取1，则先手在 [3,9] 上能得9（取9），后手得3，总分先手=2+9=11，后手=1+3=4，净胜7，与DP结果一致。

步骤7：复杂度分析

• 时间复杂度：O(n²)，因为需要计算 O(n²) 个状态，每个状态转移是 O(1)。
• 空间复杂度：O(n²)，用于存储 dp 表。可以优化到 O(n) 因为 dp[i][j] 只依赖于相邻的较短区间，但通常 n 不大时二维数组即可。

步骤8：代码框架（Python）

def stoneGameIX(piles):
    n = len(piles)
    dp = [[0]*n for _ in range(n)]
    for i in range(n):
        dp[i][i] = piles[i]
    for length in range(2, n+1):
        for i in range(n-length+1):
            j = i+length-1
            left = piles[i] - dp[i+1][j]
            right = piles[j] - dp[i][j-1]
            dp[i][j] = max(left, right)
    return dp[0][n-1]  # 返回先手净胜分

如果只需要判断先手是否不败，可以返回 dp[0][n-1] >= 0。

总结：这个题目是博弈区间DP的经典应用，通过定义“当前玩家在区间上的最大净胜分”作为状态，利用对称性和最优子结构，用简单的减法转移，就能解决这类两端取数的最优博弈问题。注意，这里的状态定义是“当前玩家”而不是“先手”，这是关键，使得转移时可以用已计算的子区间结果。