区间动态规划例题：石子游戏 IX（博弈类区间DP，取石子问题的另一种变形）

题目描述

有 n 堆石子排成一行，第 i 堆石子有 piles[i] 个。Alice 和 Bob 轮流进行自己的回合，Alice 先手。每一回合，玩家可以从行的最左侧或最右侧移除一堆石子，并获得这堆石子的数量作为自己的得分。游戏持续到所有石子都被移除。假设两位玩家都采用最优策略，问 Alice 是否能赢得比赛？换句话说，在游戏结束时，如果 Alice 的总得分严格大于 Bob 的总得分，则 Alice 获胜。如果 Alice 的得分等于或小于 Bob 的得分，则 Alice 失败。题目要求返回 True 或 False。

注意：题目中的石子数量可能为正、零或负数（但通常为自然数）。玩家目标是最大化自己的总得分，而不是像“预测赢家”问题那样只比较最终谁多。这里需要明确：Alice 的目标是在游戏结束时，自己的总得分严格大于 Bob 的总得分。在双方都最优的情况下，这等价于判断Alice 能获得的最大总得分是否大于总石子数的一半。

问题分析

1. 与预测赢家的区别

   • 预测赢家问题：只判断先手是否“非负”（即先手得分 ≥ 后手得分）。
   • 本题：判断先手是否能严格大于后手。这实际上可以转化为先手能获得的最大得分是否大于总石子数的一半。
   • 但更常用的思路是：定义 dp[i][j] 为在石子堆 piles[i..j] 上进行游戏时，当前先手玩家能比后手玩家多得的分数。如果最终 dp[0][n-1] > 0，则 Alice 获胜。

2. 状态定义
   设 dp[i][j] 表示当石子堆为 piles[i..j] 时，当前先手玩家能比后手玩家多得的分数（即先手得分减去后手得分）。

3. 状态转移

   • 如果当前先手取走 piles[i]，则剩下区间 [i+1, j] 中，后手变为先手，他在该区间能比原先后手（即当前先手）多得 dp[i+1][j] 分。
     那么当前先手取左端时，他与后手的得分差为：
     piles[i] - dp[i+1][j]
   • 如果当前先手取走 piles[j]，则剩下区间 [i, j-1] 中，后手变为先手，他在该区间能比原先后手多得 dp[i][j-1] 分。
     那么当前先手取右端时，他与后手的得分差为：
     piles[j] - dp[i][j-1]
   • 当前先手会选择对自己最有利的方式，即：

     dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
     

4. 边界条件
   当 i == j 时，只有一堆石子，当前先手取走它，后手得分为 0，所以 dp[i][i] = piles[i]。

解题步骤

1. 输入石子数组 piles，长度为 n。
2. 创建二维数组 dp[n][n]，初始化为 0。
3. 初始化对角线：dp[i][i] = piles[i]。
4. 按区间长度 len 从 2 到 n 遍历：
   • 对于每个起点 i，计算终点 j = i + len - 1。
   • 根据转移方程更新：

     dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
     

5. 最终如果 dp[0][n-1] > 0，则 Alice 获胜，返回 True；否则返回 False。

举例说明

假设 piles = [3, 9, 1, 2]，总石子数 = 15，Alice 要获得至少 8 分才能赢。

1. 初始化 dp[i][i]：

   dp[0][0] = 3
   dp[1][1] = 9
   dp[2][2] = 1
   dp[3][3] = 2
   

2. 区间长度 2：
   • i=0, j=1：dp[0][1] = max(3 - dp[1][1], 9 - dp[0][0]) = max(3-9, 9-3) = max(-6, 6) = 6
   • i=1, j=2：dp[1][2] = max(9 - dp[2][2], 1 - dp[1][1]) = max(9-1, 1-9) = max(8, -8) = 8
   • i=2, j=3：dp[2][3] = max(1 - dp[3][3], 2 - dp[2][2]) = max(1-2, 2-1) = max(-1, 1) = 1
3. 区间长度 3：
   • i=0, j=2：dp[0][2] = max(3 - dp[1][2], 1 - dp[0][1]) = max(3-8, 1-6) = max(-5, -5) = -5
   • i=1, j=3：dp[1][3] = max(9 - dp[2][3], 2 - dp[1][2]) = max(9-1, 2-8) = max(8, -6) = 8
4. 区间长度 4：
   • i=0, j=3：dp[0][3] = max(3 - dp[1][3], 2 - dp[0][2]) = max(3-8, 2-(-5)) = max(-5, 7) = 7
5. 最终 dp[0][3] = 7 > 0，Alice 获胜。

验证：Alice 先手取 3（左端），剩下 [9,1,2]；Bob 取 9（左端），剩下 [1,2]；Alice 取 2（右端），剩下 [1]；Bob 取 1。得分：Alice=3+2=5，Bob=9+1=10，Alice 实际输。矛盾？
注意：上述 DP 计算的是在双方都最优的情况下，当前先手能比后手多得的分数。但我们的计算是基于“当前先手总是选择最优”，而刚才的手动推演中，Bob 在第二步没有选择最优（他应取 2 而不是 9）。

重新推演最优策略：

• Alice 先手，她可以选择左 3 或右 2。
  如果选左 3，则 Bob 面对 [9,1,2]，Bob 作为先手，在 [9,1,2] 上计算 dp[1][3] 我们已得 8 > 0，意味着 Bob 在子游戏中能赢 Alice（在该子游戏中比 Alice 多得 8 分），所以 Alice 选左 3 会输。
  如果选右 2，则 Bob 面对 [3,9,1]，计算 dp[0][2] 我们已得 -5 < 0，意味着 Bob 在该子游戏中会比 Alice 少得 5 分，即 Alice 能赢。
  所以 Alice 应选右 2，之后 Bob 无论怎么选，Alice 都能保持优势。最终 Alice 总得分可大于 Bob。
  因此 DP 结果 dp[0][3] = 7 > 0 正确表示 Alice 能赢。

代码实现（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
            dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
    return dp[0][n-1] > 0

复杂度分析

• 时间复杂度：O(n²)，需要填满 n×n 的 DP 表。
• 空间复杂度：O(n²)，可以优化到 O(n) 用一维数组，但为清晰起见这里用二维。

要点总结

1. 定义 dp[i][j] 为当前先手在区间 [i, j] 上能比后手多得的分数。
2. 转移时考虑取左端或右端，用当前石子数减去在剩余区间上后手变为先手时的得分差。
3. 最终若 dp[0][n-1] > 0，则先手（Alice）能获胜。

这个解法是博弈类区间 DP 的典型应用，关键在于理解“得分差”的传递与转换。