“石子游戏 III” 问题
字数 2468 2025-12-15 18:47:10

“石子游戏 III” 问题

题目描述：
你面前有一行排成数组的石子堆，用整数数组 stoneValue 表示，其中 stoneValue[i] 表示第 i 堆石子的价值。Alice 和 Bob 轮流进行游戏，Alice 先手。在每个玩家的回合中，玩家可以从剩下的石子堆的最左端取走 1、2 或 3 堆石子。游戏持续到没有石子堆剩下为止。玩家的得分是他取走的所有石子堆的价值之和。每个玩家都会采取最优策略，目标是最大化自己的得分，并且假设双方都发挥最佳水平。最终得分较高的玩家获胜。如果两者得分相同，则游戏平局。问：在双方都发挥最佳水平的情况下，Alice 是赢、输还是平局？

示例：
输入：stoneValue = [1,2,3,7]
输出："Bob" （解释：Alice 取前三堆得分为 6，Bob 取最后一堆得分为 7，Bob 胜）

解题过程：

这个问题本质是一个零和博弈，可以用区间动态规划（记忆化搜索）来解决。我们将问题定义在一个区间上，表示当前剩下从索引 i 到末尾的石子堆，当前轮到某个玩家行动时，该玩家能获得的最大净胜分数（即当前玩家的得分减去对方得分的差值）。

1. 定义状态和子问题

设 dp[i] 表示：当剩下的石子堆是 stoneValue[i:]（从索引 i 到末尾）时，当前行动的玩家能获得的最大净胜分数。

注意：这里“当前行动的玩家”可能是 Alice 或 Bob，但因为是零和博弈，我们只关心净胜分数。如果当前是 Alice 行动，那么最终 Alice 得分减去 Bob 得分 = dp[i]；如果当前是 Bob 行动，那么 Bob 得分减去 Alice 得分 = dp[i]。但为了统一，我们规定 dp[i] 总是表示当前行动的玩家的得分减去对方得分。

2. 状态转移

在位置 i，当前玩家可以选择取走 1 堆、2 堆或 3 堆石子（假设剩余堆数足够）。设取走的堆数记为 x（x=1,2,3），则：

  • 取走的石子总价值为 sum(i, i+x-1)（即从 i 到 i+x-1 的和）。
  • 之后轮到对手在位置 i+x 开始行动，对手的最大净胜分数为 dp[i+x]（注意这是从对手视角的净胜分数）。

对于当前玩家来说，在取走这 x 堆后，总得分差是多少呢？

当前玩家得分增加了 sum(i, i+x-1)，而对手在后续游戏中会有净胜分数 dp[i+x]（对手得分减去当前玩家得分）。因此，当前玩家的净胜分数 = 当前取走的得分 - 对手在后续的净胜分数。即：

\[dp[i] = \max_{x=1,2,3} \left( \text{sum}(i, i+x-1) - dp[i+x] \right) \]

其中 sum(i, j) 表示 stoneValue[i] + ... + stoneValue[j]。

3. 边界条件

如果 i 已经超出数组长度 n，表示没有石子堆剩下，当前玩家没有得分，对手也没有得分，净胜分数为 0。即：

\[dp[n] = 0 \]

4. 计算顺序

由于 dp[i] 依赖于 dp[i+x]（x>0），即依赖于更大的索引，所以我们应该从后向前计算，i 从 n-1 到 0。

5. 最终结果

初始时，i=0，当前行动的玩家是 Alice，所以 dp[0] 表示 Alice 的得分减去 Bob 得分的最大净胜分数。

  • 如果 dp[0] > 0，Alice 净胜分为正，Alice 赢。
  • 如果 dp[0] < 0，Alice 净胜分为负，即 Bob 净胜分为正，Bob 赢。
  • 如果 dp[0] = 0，平局。

6. 优化与实现细节

  • 为了快速求区间和，可以用前缀和数组 prefix，其中 prefix[i] 表示前 i 个元素的和（prefix[0]=0），那么 sum(i, j) = prefix[j+1] - prefix[i]。
  • 时间复杂度 O(n)，空间复杂度 O(n)。

举个例子：stoneValue = [1,2,3,7]

n=4，前缀和 prefix=[0,1,3,6,13]。

从后向前计算：

  • i=4: dp[4]=0
  • i=3: 只能取 1 堆（因为只剩一堆）
    • x=1: sum(3,3)=7, dp[4]=0 → 7-0=7
      dp[3]=7
  • i=2: 可选 1~3 堆
    • x=1: sum(2,2)=3, dp[3]=7 → 3-7=-4
    • x=2: sum(2,3)=3+7=10, dp[4]=0 → 10-0=10
      dp[2]=max(-4,10)=10
  • i=1: 可选 1~3 堆
    • x=1: sum(1,1)=2, dp[2]=10 → 2-10=-8
    • x=2: sum(1,2)=2+3=5, dp[3]=7 → 5-7=-2
    • x=3: sum(1,3)=2+3+7=12, dp[4]=0 → 12-0=12
      dp[1]=max(-8,-2,12)=12
  • i=0: 可选 1~3 堆
    • x=1: sum(0,0)=1, dp[1]=12 → 1-12=-11
    • x=2: sum(0,1)=1+2=3, dp[2]=10 → 3-10=-7
    • x=3: sum(0,2)=1+2+3=6, dp[3]=7 → 6-7=-1
      dp[0]=max(-11,-7,-1)=-1

dp[0] = -1 < 0，所以 Bob 赢。

验证：Alice 最优取前三堆得 6 分，Bob 取最后一堆得 7 分，Bob 胜 1 分，净胜分 -1 对 Alice 符合。

总结：这个问题是区间 DP 的一个典型博弈应用，状态定义为当前玩家在剩余区间上的最大净胜分，转移时考虑取 1~3 堆后的局面，用前缀和加速区间和计算。最后根据 dp[0] 的正负判断胜负。

“石子游戏 III” 问题 题目描述： 你面前有一行排成数组的石子堆，用整数数组 stoneValue 表示，其中 stoneValue[i] 表示第 i 堆石子的价值。Alice 和 Bob 轮流进行游戏，Alice 先手。在每个玩家的回合中，玩家可以从剩下的石子堆的 最左端 取走 1、2 或 3 堆石子。游戏持续到没有石子堆剩下为止。玩家的得分是他取走的所有石子堆的价值之和。每个玩家都会采取最优策略，目标是最大化自己的得分，并且假设双方都发挥最佳水平。最终得分较高的玩家获胜。如果两者得分相同，则游戏平局。问：在双方都发挥最佳水平的情况下，Alice 是赢、输还是平局？ 示例： 输入： stoneValue = [1,2,3,7] 输出： "Bob" （解释：Alice 取前三堆得分为 6，Bob 取最后一堆得分为 7，Bob 胜） 解题过程： 这个问题本质是一个零和博弈，可以用区间动态规划（记忆化搜索）来解决。我们将问题定义在一个区间上，表示当前剩下从索引 i 到末尾的石子堆，当前轮到某个玩家行动时，该玩家能获得的最大净胜分数（即当前玩家的得分减去对方得分的差值）。 1. 定义状态和子问题 设 dp[i] 表示：当剩下的石子堆是 stoneValue[i:] （从索引 i 到末尾）时， 当前行动的玩家 能获得的最大净胜分数。 注意：这里“当前行动的玩家”可能是 Alice 或 Bob，但因为是零和博弈，我们只关心净胜分数。如果当前是 Alice 行动，那么最终 Alice 得分减去 Bob 得分 = dp[i] ；如果当前是 Bob 行动，那么 Bob 得分减去 Alice 得分 = dp[i] 。但为了统一，我们规定 dp[i] 总是表示 当前行动的玩家 的得分减去对方得分。 2. 状态转移 在位置 i，当前玩家可以选择取走 1 堆、2 堆或 3 堆石子（假设剩余堆数足够）。设取走的堆数记为 x （x=1,2,3），则： 取走的石子总价值为 sum(i, i+x-1) （即从 i 到 i+x-1 的和）。 之后轮到对手在位置 i+x 开始行动，对手的最大净胜分数为 dp[i+x] （注意这是从对手视角的净胜分数）。 对于当前玩家来说，在取走这 x 堆后，总得分差是多少呢？ 当前玩家得分增加了 sum(i, i+x-1) ，而对手在后续游戏中会有净胜分数 dp[i+x] （对手得分减去当前玩家得分）。因此，当前玩家的净胜分数 = 当前取走的得分 - 对手在后续的净胜分数。即： \[ dp[ i] = \max_ {x=1,2,3} \left( \text{sum}(i, i+x-1) - dp[ i+x ] \right) \] 其中 sum(i, j) 表示 stoneValue[i] + ... + stoneValue[j] 。 3. 边界条件 如果 i 已经超出数组长度 n，表示没有石子堆剩下，当前玩家没有得分，对手也没有得分，净胜分数为 0。即： \[ dp[ n ] = 0 \] 4. 计算顺序 由于 dp[i] 依赖于 dp[i+x] （x>0），即依赖于更大的索引，所以我们应该从后向前计算，i 从 n-1 到 0。 5. 最终结果 初始时，i=0，当前行动的玩家是 Alice，所以 dp[0] 表示 Alice 的得分减去 Bob 得分的最大净胜分数。 如果 dp[0] > 0 ，Alice 净胜分为正，Alice 赢。 如果 dp[0] < 0 ，Alice 净胜分为负，即 Bob 净胜分为正，Bob 赢。 如果 dp[0] = 0 ，平局。 6. 优化与实现细节 为了快速求区间和，可以用前缀和数组 prefix ，其中 prefix[i] 表示前 i 个元素的和（prefix[ 0]=0），那么 sum(i, j) = prefix[j+1] - prefix[i] 。 时间复杂度 O(n)，空间复杂度 O(n)。 举个例子 ： stoneValue = [1,2,3,7] n=4，前缀和 prefix=[ 0,1,3,6,13 ]。 从后向前计算： i=4: dp[ 4 ]=0 i=3: 只能取 1 堆（因为只剩一堆） x=1: sum(3,3)=7, dp[ 4 ]=0 → 7-0=7 dp[ 3 ]=7 i=2: 可选 1~3 堆 x=1: sum(2,2)=3, dp[ 3 ]=7 → 3-7=-4 x=2: sum(2,3)=3+7=10, dp[ 4 ]=0 → 10-0=10 dp[ 2 ]=max(-4,10)=10 i=1: 可选 1~3 堆 x=1: sum(1,1)=2, dp[ 2 ]=10 → 2-10=-8 x=2: sum(1,2)=2+3=5, dp[ 3 ]=7 → 5-7=-2 x=3: sum(1,3)=2+3+7=12, dp[ 4 ]=0 → 12-0=12 dp[ 1 ]=max(-8,-2,12)=12 i=0: 可选 1~3 堆 x=1: sum(0,0)=1, dp[ 1 ]=12 → 1-12=-11 x=2: sum(0,1)=1+2=3, dp[ 2 ]=10 → 3-10=-7 x=3: sum(0,2)=1+2+3=6, dp[ 3 ]=7 → 6-7=-1 dp[ 0 ]=max(-11,-7,-1)=-1 dp[ 0] = -1 < 0，所以 Bob 赢。 验证：Alice 最优取前三堆得 6 分，Bob 取最后一堆得 7 分，Bob 胜 1 分，净胜分 -1 对 Alice 符合。 总结 ：这个问题是区间 DP 的一个典型博弈应用，状态定义为当前玩家在剩余区间上的最大净胜分，转移时考虑取 1~3 堆后的局面，用前缀和加速区间和计算。最后根据 dp[ 0 ] 的正负判断胜负。