石子游戏 VI

字数 2693 2025-12-06 05:21:18

石子游戏 VI

题目描述

Alice 和 Bob 轮流从一行 n 堆石子中取石子。这 n 堆石子排成一行，每堆石子有一个价值 values[i]。游戏规则如下：

Alice 先手，Bob 后手，两人轮流进行。
在每一轮中，当前玩家必须从当前剩余石子堆的最左边或最右边取走一堆石子，并获得这堆石子的价值。
当所有石子堆都被取完后，游戏结束。
玩家的最终得分是他所取石子堆的价值总和。得分高的玩家获胜。假设 Alice 和 Bob 都发挥出最佳水平，都希望最大化自己的得分与对手得分的差值（即自己的净胜分）。如果 Alice 的净胜分为正，则 Alice 获胜；否则 Bob 获胜。

给定一个整数数组 values，请判断在双方都采取最优策略的情况下，Alice 是否能够获胜。如果 Alice 的净胜分大于或等于 0，则返回 True，否则返回 False。

示例 1：
输入：values = [1, 3, 7]
输出：True
解释：

如果 Alice 先取 1（左端），则剩下 [3, 7]。Bob 会取 7（右端）。然后 Alice 取 3。Alice 总分 4，Bob 总分 7，Alice 净胜分 -3，输。
如果 Alice 先取 7（右端），则剩下 [1, 3]。Bob 会取 3（右端）。然后 Alice 取 1。Alice 总分 8，Bob 总分 3，Alice 净胜分 5，赢。
所以 Alice 的最优选择是取 7，她能赢。

解题过程

这是一个典型的零和博弈问题，可以用区间动态规划解决。我们关注的是在给定的石子序列区间上，先手玩家能比后手玩家多得多少分。

定义状态
定义 dp[i][j] 表示当石子堆只剩下下标从 i 到 j 的这一段连续区间时（i <= j），当前将要行动的玩家（先手玩家）在这一轮及之后的所有轮次中，能够获得的最大净胜分（即“先手玩家能获得的总分”减去“后手玩家能获得的总分”）。
状态转移方程
考虑区间 [i, j]，当前是先手玩家的回合。他有两种选择：
- 选择取走最左边的石子堆 values[i]。那么他会立即获得 values[i] 分。接着，区间变为 [i+1, j]，轮到后手玩家行动。在子问题 [i+1, j] 中，原来的后手玩家变成了“先手玩家”。根据定义，在子问题 [i+1, j] 中，这位“新先手玩家”能获得的最大净胜分是 dp[i+1][j]。
  但是请注意，dp[i+1][j] 的定义是“新先手玩家的得分”减去“新后手玩家的得分”。在父问题 [i, j] 中，当前行动者（我们）在取了 values[i] 后，就变成了子问题中的“新后手玩家”。
  因此，如果我们选择左边，最终的净胜分计算如下：
  我们（当前玩家）得分 = values[i] + （我们在子问题中作为后手玩家的得分）。
  对手（下一位玩家）得分 = （对手在子问题中作为先手玩家的得分）。
  所以，我们（当前玩家）的净胜分 = (values[i] + 我们在子问题中作为后手玩家的得分) - (对手在子问题中作为先手玩家的得分)。
  由于在子问题 [i+1, j] 中，净胜分 dp[i+1][j] = (新先手玩家得分) - (新后手玩家得分) = (对手得分) - (我们得分)。
  那么，我们作为后手玩家在子问题中的得分 = 对手得分 - dp[i+1][j]。
  将这个关系代入上式：
  我们的净胜分 = values[i] + (对手得分 - dp[i+1][j]) - 对手得分 = values[i] - dp[i+1][j]。
- 选择取走最右边的石子堆 values[j]。同理，净胜分 = values[j] - dp[i][j-1]。
因为当前玩家是绝对理性的，他会选择使自己净胜分最大化的操作。所以状态转移方程为：
dp[i][j] = max(values[i] - dp[i+1][j], values[j] - dp[i][j-1])
初始条件与边界
- 当区间长度为 1，即 i == j 时，只有一堆石子。先手玩家直接取走，获得 values[i] 分，后手玩家得 0 分。净胜分就是 values[i]。
  所以，dp[i][i] = values[i]。
计算顺序
我们需要从小区间向大区间计算。因为 dp[i][j] 依赖于 dp[i+1][j] 和 dp[i][j-1]，即依赖于长度更短的区间。
我们可以按区间长度 len 从 1 遍历到 n。对于每个长度 len，枚举所有可能的起点 i，计算出终点 j = i + len - 1。
最终答案
整个游戏开始时，石子区间是 [0, n-1]，Alice 是先手玩家。所以，如果 dp[0][n-1] >= 0，则意味着 Alice 作为先手，在最优策略下，她的净胜分非负，她可以获胜（或打平），返回 True；否则返回 False。
举例演算
以 values = [1, 3, 7] 为例，n = 3。
- 初始化：dp[0][0]=1, dp[1][1]=3, dp[2][2]=7。
- 长度 len = 2：
  - 区间 [0,1]: dp[0][1] = max(1 - dp[1][1], 3 - dp[0][0]) = max(1-3, 3-1) = max(-2, 2) = 2。
  - 区间 [1,2]: dp[1][2] = max(3 - dp[2][2], 7 - dp[1][1]) = max(3-7, 7-3) = max(-4, 4) = 4。
- 长度 len = 3：
  - 区间 [0,2]: dp[0][2] = max(1 - dp[1][2], 7 - dp[0][1]) = max(1-4, 7-2) = max(-3, 5) = 5。
- 最终 dp[0][2] = 5 > 0，所以 Alice 获胜，返回 True。

这就是“石子游戏 VI”问题的区间动态规划解法。其核心在于定义 dp[i][j] 为当前先手玩家在区间 [i,j] 上的净胜分，并通过对方在子问题中的最优表现（即子问题的 dp 值）来推导当前的选择。最终判断全局的净胜分即可。

石子游戏 VI 题目描述 Alice 和 Bob 轮流从一行 n 堆石子中取石子。这 n 堆石子排成一行，每堆石子有一个价值 values[i] 。游戏规则如下： Alice 先手，Bob 后手，两人轮流进行。在每一轮中，当前玩家必须从当前剩余石子堆的最左边或最右边取走一堆石子，并获得这堆石子的价值。当所有石子堆都被取完后，游戏结束。玩家的最终得分是他所取石子堆的价值总和。得分高的玩家获胜。假设 Alice 和 Bob 都发挥出最佳水平，都希望最大化自己的得分与对手得分的差值（即自己的净胜分）。如果 Alice 的净胜分为正，则 Alice 获胜；否则 Bob 获胜。给定一个整数数组 values ，请判断在双方都采取最优策略的情况下，Alice 是否能够获胜。如果 Alice 的净胜分大于或等于 0，则返回 True ，否则返回 False 。示例 1：输入： values = [1, 3, 7] 输出： True 解释：如果 Alice 先取 1（左端），则剩下 [3, 7] 。Bob 会取 7（右端）。然后 Alice 取 3。Alice 总分 4，Bob 总分 7，Alice 净胜分 -3，输。如果 Alice 先取 7（右端），则剩下 [1, 3] 。Bob 会取 3（右端）。然后 Alice 取 1。Alice 总分 8，Bob 总分 3，Alice 净胜分 5，赢。所以 Alice 的最优选择是取 7，她能赢。解题过程这是一个典型的零和博弈问题，可以用区间动态规划解决。我们关注的是在给定的石子序列区间上，先手玩家能比后手玩家多得多少分。定义状态定义 dp[i][j] 表示当石子堆只剩下下标从 i 到 j 的这一段连续区间时（ i <= j ），当前将要行动的玩家（先手玩家）在这一轮及之后的所有轮次中，能够获得的最大净胜分（即“先手玩家能获得的总分”减去“后手玩家能获得的总分”）。状态转移方程考虑区间 [i, j] ，当前是先手玩家的回合。他有两种选择：选择取走最左边的石子堆 values[i] 。那么他会立即获得 values[i] 分。接着，区间变为 [i+1, j] ，轮到后手玩家行动。在子问题 [i+1, j] 中，原来的后手玩家变成了“先手玩家”。根据定义，在子问题 [i+1, j] 中，这位“新先手玩家”能获得的最大净胜分是 dp[i+1][j] 。但是请注意， dp[i+1][j] 的定义是“新先手玩家的得分”减去“新后手玩家的得分”。在父问题 [i, j] 中，当前行动者（我们）在取了 values[i] 后，就变成了子问题中的“新后手玩家”。因此，如果我们选择左边，最终的净胜分计算如下：我们（当前玩家）得分 = values[i] + （我们在子问题中作为后手玩家的得分）。对手（下一位玩家）得分 = （对手在子问题中作为先手玩家的得分）。所以，我们（当前玩家）的净胜分 = ( values[i] + 我们在子问题中作为后手玩家的得分) - (对手在子问题中作为先手玩家的得分)。由于在子问题 [i+1, j] 中，净胜分 dp[i+1][j] = (新先手玩家得分) - (新后手玩家得分) = (对手得分) - (我们得分)。那么，我们作为后手玩家在子问题中的得分 = 对手得分 - dp[i+1][j] 。将这个关系代入上式：我们的净胜分 = values[i] + (对手得分 - dp[i+1][j] ) - 对手得分 = values[i] - dp[i+1][j] 。选择取走最右边的石子堆 values[j] 。同理，净胜分 = values[j] - dp[i][j-1] 。因为当前玩家是绝对理性的，他会选择使自己净胜分最大化的操作。所以状态转移方程为： dp[i][j] = max(values[i] - dp[i+1][j], values[j] - dp[i][j-1]) 初始条件与边界当区间长度为 1，即 i == j 时，只有一堆石子。先手玩家直接取走，获得 values[i] 分，后手玩家得 0 分。净胜分就是 values[i] 。所以， dp[i][i] = values[i] 。计算顺序我们需要从小区间向大区间计算。因为 dp[i][j] 依赖于 dp[i+1][j] 和 dp[i][j-1] ，即依赖于长度更短的区间。我们可以按区间长度 len 从 1 遍历到 n。对于每个长度 len ，枚举所有可能的起点 i ，计算出终点 j = i + len - 1 。最终答案整个游戏开始时，石子区间是 [0, n-1] ，Alice 是先手玩家。所以，如果 dp[0][n-1] >= 0 ，则意味着 Alice 作为先手，在最优策略下，她的净胜分非负，她可以获胜（或打平），返回 True ；否则返回 False 。举例演算以 values = [1, 3, 7] 为例， n = 3 。初始化： dp[0][0]=1 , dp[1][1]=3 , dp[2][2]=7 。长度 len = 2 ：区间 [0,1] : dp[0][1] = max(1 - dp[1][1], 3 - dp[0][0]) = max(1-3, 3-1) = max(-2, 2) = 2 。区间 [1,2] : dp[1][2] = max(3 - dp[2][2], 7 - dp[1][1]) = max(3-7, 7-3) = max(-4, 4) = 4 。长度 len = 3 ：区间 [0,2] : dp[0][2] = max(1 - dp[1][2], 7 - dp[0][1]) = max(1-4, 7-2) = max(-3, 5) = 5 。最终 dp[0][2] = 5 > 0 ，所以 Alice 获胜，返回 True 。这就是“石子游戏 VI”问题的区间动态规划解法。其核心在于定义 dp[i][j] 为当前先手玩家在区间 [i,j] 上的净胜分，并通过对方在子问题中的最优表现（即子问题的 dp 值）来推导当前的选择。最终判断全局的净胜分即可。