石子游戏 VIII（博弈类区间DP，取石子问题的另一种变形）
字数 6409 2025-12-07 12:40:43

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

我们先明确题目：
有 n 堆石子排成一行，第 i 堆石子有 stones[i] 个。两名玩家轮流操作，每次从当前最左边非空的石子堆中取走任意正整数个石子（至少 1 个，至多全取），取完后如果这堆石子空了，就把它从行中移除。游戏继续从左到右的第一堆非空石子堆。
当没有石子可取时游戏结束，此时当前要操作的玩家判负（即无法操作的人输）。
假设两人都采用最优策略，问先手是否必胜。
（这其实是一个经典的“取石子”游戏的线性排列版本，但我们可以用区间 DP 的思维分析它。）

第一步：把问题转化为可处理的模型

  • 石子堆从左到右是 stones[0] … stones[n-1]。
  • 每次必须从最左边非空堆取任意正整数个（1 到全部）。
  • 取空后该堆消失，下一堆成为新的最左边。
  • 无法操作（即没有石子剩下）的玩家输。

这等价于：
假设当前剩下石子堆的区间是 [l, r]（0 ≤ l ≤ r < n），先手必须对 stones[l] 进行操作：

  1. 先手可以从 stones[l] 中取走 k 个（1 ≤ k ≤ stones[l]）。
  2. 如果 k = stones[l]，则剩下 stones[l] 为空，于是堆区间变成 [l+1, r]。
  3. 如果 k < stones[l]，则 stones[l] 剩下 stones[l] - k 个石子，堆区间还是 [l, r]，但最左边堆的数量变了。

注意：当 k < stones[l] 时，这堆还在，只是数量减少，所以下次对方仍然必须对这一堆操作，直到它被取完。

于是对于一堆石子来说，如果只剩它自己，那么先手直接全取就赢了。
但如果有后续堆，情况就复杂，因为取的数量会影响后续的胜负。

第二步：定义状态

一种更简洁的转化：
我们可以把每堆的石子数看作一个正整数，游戏的过程是必须从最左边非空堆取走至少 1 个，然后可以选择取完它（进入下一堆）或不取完（留在本堆）。
为了方便 DP，我们定义：

  • dp[l][r] 表示：石子堆区间是 [l, r] 时，当前要操作的玩家（不一定是原始的先手）是否必胜（True/False）。

初始情况：

  • 如果区间为空（l > r），当前玩家没有可取的，必败（False）。
  • 如果区间只有一堆 l==r，那么当前玩家可以一次全取完，取完后对手面对空区间，对手必败，所以当前玩家必胜（True）。

第三步：状态转移

我们要计算 dp[l][r]。

当前玩家必须对 stones[l] 操作，假设 stones[l] 剩余 S 个（初始 S = stones[l]）。

他可以取走 t 个（1 ≤ t ≤ S）。
取 t 个后，这堆剩下 S - t 个石子。

分两种情况：

  1. t = S（全取完）：
    取完后堆 l 消失，区间变成 [l+1, r]。
    接下来是对方在 [l+1, r] 上操作，我们查询 dp[l+1][r] 表示对方在新区间上是否必胜。
    如果 dp[l+1][r] 是 False（对方必败），那么我们这种取法就导致我们胜利（因为对手面对必败局面，我们胜利）。
    所以只要存在一种 t = S 使得 dp[l+1][r] = False，那么 dp[l][r] = True。

  2. t < S（没取完）：
    取完后堆 l 还在，但石子数变成 S - t。
    注意：此时区间依然是 [l, r]，但下一轮是对方操作，而且对方仍然必须对堆 l 操作（因为它没空），但对方面临的局面是石子数比原来少的同一个堆。
    这相当于：我们先手取走 t 个后，轮到对方在“同一堆数量减少”的情况下操作。这其实可以看作是一个子游戏，但石子数变化，似乎和 l,r 没关系？
    其实我们可以换个思路：这种“没取完”的情况，等价于先手取走一部分后，交换了先后手角色，但堆还在，所以可以递归到“同一堆数量减少”的同一区间？
    不，这里的关键是：当没取完时，堆 l 还是堆 l，只是数量变了，我们可以用另一个维度表示数量，但这样状态太多。

我们可以简化模型：
注意到，对于一堆来说，如果它后面还有堆，那么它的“必胜/必败”不仅仅由它的数量决定，还由后面的堆的胜负决定。
有一个经典技巧：定义 dp[l] 表示：考虑从 l 到 n-1 这些堆，当前要操作的玩家是否必胜（假设 l 堆数量是 stones[l]）。

第四步：一维 DP 解法

设 n 是石子堆数。
定义 dp[i] 表示：只考虑从 i 到 n-1 这些堆（且第 i 堆是原数量 stones[i]），当前要操作的人是否必胜。

基础情况：

  • 如果没有堆了（i == n），dp[n] = False（必败，因为没有石子可取）。
  • 如果 i == n-1（最后一堆），那么当前玩家可以一次全取完，对方没得取，所以 dp[n-1] = True。

对于 i 从 n-2 到 0 计算：
我们面对 stones[i]，我们必须从它取 1 到 stones[i] 个石子。

  1. 如果我们可以一次全取完（t = stones[i]），那么取完后轮到对方在 i+1 堆开始操作。
    即对方面对的局面是 dp[i+1]。
    如果 dp[i+1] 是 False，说明对方必败，那么我们这种操作就赢，所以 dp[i] 可能为 True。

  2. 如果我们不一次全取完（t < stones[i]），那么取 t 个后，第 i 堆还剩 stones[i] - t 个石子，仍然在位置 i，轮到对方操作。
    但此时对方的局面是：同一堆 i 数量减少。
    注意，对于对方来说，此时他面对的是相同索引 i 但石子数更少的情况，这实际上等价于一个新的游戏，起始就是 stones[i]-t 个石子在堆 i，后面是 stones[i+1]…stones[n-1]。

    也就是说，如果定义 f(s, i) 为“堆 i 当前数量为 s，后面堆是 stones[i+1]…stones[n-1]，当前要操作的人是否必胜”，那么我们的 DP 可以扩展到二维 s 和 i，但 s 最大是 stones[i]，状态数总和是 O(sum(stones) + n)，可能很大。

但是，这里有一个经典结论（Nim 的变形）：
当面对一堆石子数量 s 且后面有其它堆时，当前玩家可以取 1 到 s 个，如果取完后剩下 s' 个（s'>=0），那么：

  • 如果 s'=0，则交给对方在 i+1 堆开始；
  • 如果 s'>0，则交给对方在同一堆 i 但数量为 s' 的局面。

所以我们用二维 dp[i][s] 表示“从第 i 堆开始，且第 i 堆当前石子数为 s（1 ≤ s ≤ stones[i]），当前玩家是否必胜”。

初始化：

  • dp[i][0] 表示第 i 堆已空，所以等价于 dp[i+1][stones[i+1]]（即从下一堆原数量开始）。
  • 为了方便，定义 win(i) = dp[i][stones[i]] 表示第 i 堆是原数量时的胜负。

计算 dp[i][s]（s 从 1 到 stones[i]）：
当前玩家可以取 1 到 s 个石子，取 k 个后剩下 s-k 个：

  • 如果 s-k = 0，则轮到对方在 i+1 堆原数量开始，即局面是 win(i+1)。
  • 如果 s-k > 0，则轮到对方在 dp[i][s-k] 的局面。

于是：
dp[i][s] = True 当且仅当 存在 k ∈ {1,…,s} 使得：
若 s-k==0，则 win(i+1) = False；
若 s-k>0，则 dp[i][s-k] = False。

这个递推可以从 s 从小到大计算，因为 dp[i][s-k] 的 s-k 更小。

第五步：简化递推

从上述规则发现，dp[i][s] 只和 dp[i][小于s的数] 以及 win(i+1) 有关。
我们可以计算 win(i) = dp[i][stones[i]]。

推导边界：

  • 对于最后一堆 i = n-1：
    无论 s 是多少，如果 s>0，当前玩家全取完（k=s），则对方在 i+1=n 堆（空）必败，所以当前必胜。
    所以 dp[n-1][s] = True 对所有 s≥1。
    特别地，win(n-1) = True。

  • 对于 i < n-1：
    我们计算 dp[i][1]：
    s=1，只能取 k=1，取完 s-k=0，所以局面交给 win(i+1)。
    所以 dp[i][1] = True 当且仅当 win(i+1) = False。

    然后 s=2 时，可取的 k=1 或 2：

    • 取 1 剩 1 -> 对方 dp[i][1]
    • 取 2 剩 0 -> 对方 win(i+1)
      所以 dp[i][2] = True 当且仅当 (dp[i][1] = False) 或 (win(i+1) = False) 至少一个成立。

推广：
dp[i][s] = not ( 所有可能的下一步都是对手的必胜局面 )。
下一步的可能是：
对手局面集合 = { dp[i][s-1], dp[i][s-2], …, dp[i][0?] 注意 dp[i][0] 就是 win(i+1) } 中对应 k=1..s 的那些。

更简单的规律：
定义 mex 为最小的非负整数不在集合中，但这里是布尔值，其实就是看是否存在一个 k 使得对手局面是必败。

其实可以发现，对于固定 i，dp[i][s] 的值随着 s 增加，会出现周期为 2 的模式，如果 win(i+1)=True 则 dp[i][奇数]=False, dp[i][偶数]=True 之类的。但我们可以直接递推。

第六步：直接计算 win(i) 的递推

我们可以发现，其实不需要所有 s，只需要知道 win(i) 即可。

观察：
dp[i][s] 的值只取决于 win(i+1) 和 dp[i][1…s-1]。
可以计算几个例子找规律，但已知结论（来自取石子游戏“取火柴”单堆但必须取至少1个，但这里后面还有堆）是：

定理：
定义 g[i] = win(i)（True/False）。
那么：

  • g[n] = False（没有堆，必败）。

  • g[i] 的计算：
    我们看从 stones[i] 开始，可以转移到：

    1. 全取完 → 对方局面 g[i+1]。
    2. 取一部分剩 s' (1 ≤ s' < stones[i]) → 对方局面 dp[i][s']。

    而 dp[i][s'] 的计算依赖更小的 s'，我们可以从 s=1 往上推出 dp[i][*]，然后得到 g[i]。

    但更简单结论（经推导可得）：
    g[i] = True 当且仅当 (stones[i] > 1) 或 (stones[i] == 1 且 g[i+1] = False)。

    举例验证：
    n=1, stones=[1]: g[1]不存在，g[0]：stones[0]=1，g[1]=False → g[0]=True。正确，因为先手一次取完就赢。
    n=2, stones=[1,1]: g[2]=False, g[1]: stones[1]=1 且 g[2]=False → g[1]=True。
    g[0]: stones[0]=1 且 g[1]=True → g[0]=False。正确，因为[1,1]先手必败。

    但这是错的，我们实际模拟 [1,1]：
    先手取第一堆 1 个，第一堆空，后手面对 [1]，后手取完胜，先手输，所以 g[0]=False 对。
    但公式 stones[i]>1 时 g[i]=True 吗？
    看 [2,1]：
    g[2]=False（最后一堆[1]必胜），g[1]: stones[1]=1 且 g[2]=False → g[1]=True。
    g[0]: stones[0]=2 (>1) → g[0]=True。验证：先手面对[2,1]，可以取第一堆 1 个剩 1 个，对方面对[1,1]，上面已知[1,1]先手败，所以对方败，我们胜。是的。

    看来公式是：
    g[i] = (stones[i] > 1) 或者 (stones[i] == 1 且 g[i+1] == False)。
    即：如果 stones[i] 是 1，则 g[i] = not g[i+1]；如果 stones[i] > 1，则 g[i] = True。

    验证 [1,2]：
    g[2] 最后一堆[2]，g[2]=True（因为>1）。
    g[1]: stones[1]=2>1 → True。
    g[0]: stones[0]=1 且 g[1]=True → g[0]=False。
    模拟：先手面对[1,2]，只能取第一堆 1 个，剩下[2]，后手一次取完胜，先手败，对。

第七步：最终算法

这样我们得到一个 O(n) 算法：

  1. 初始化 g[n] = False。
  2. 从 i = n-1 到 0：
    • 如果 stones[i] > 1，g[i] = True。
    • 如果 stones[i] == 1，g[i] = not g[i+1]。
  3. 答案就是 g[0]。

为什么 stones[i] > 1 时必胜？
因为先手可以控制：

  • 如果 g[i+1] = True（对方在下一堆先手必胜），那么我们可以不一次取完 stones[i]，只取 stones[i]-1 个，剩 1 个给对方，这样对方必须取这最后 1 个，取完后轮到我们在下一堆先手（即 g[i+1] 的局面），但 g[i+1] 表示下一堆当前玩家（现在是对方）必胜，但对方取完 1 个后，下一堆的当前玩家变成我们，所以我们是那个“必胜”的玩家。
    这里需要小心角色交换，其实推导结果是：剩 1 个给对方，对方取完后，我们变成下一堆的先手，而 g[i+1]=True 表示下一堆的先手必胜，所以我们必胜。

  • 如果 g[i+1] = False，那更简单，我们直接全取完 stones[i]，让对方在下一堆先手并面对必败局面，我们就赢了。
    所以无论如何 stones[i]>1 时先手必胜。

stones[i]==1 时，我们只能取完，所以局面完全交给 g[i+1] 的对手，所以 g[i] = not g[i+1]。

第八步：例子验证

例：stones = [1,1,2]
n=3
g[3]=False
i=2: stones[2]=2>1 → g[2]=True
i=1: stones[1]=1 → g[1] = not g[2] = False
i=0: stones[0]=1 → g[0] = not g[1] = True
所以先手必胜。

模拟：
先手面对[1,1,2]，先手取第一堆 1 个→剩[1,2]给后手。
后手面对[1,2]，后手必须取第一堆 1 个→剩[2]给先手。
先手面对[2]，取 2 个完胜。先手胜，符合。

这样我们就用一维 DP 和博弈推导解决了这个“必须取最左边堆”的取石子游戏。

石子游戏 VIII（博弈类区间DP，取石子问题的另一种变形） 我们先明确题目： 有 n 堆石子排成一行，第 i 堆石子有 stones[ i] 个。两名玩家轮流操作，每次从当前最左边 非空 的石子堆中取走任意正整数个石子（至少 1 个，至多全取），取完后如果这堆石子空了，就把它从行中移除。游戏继续从左到右的第一堆非空石子堆。 当没有石子可取时游戏结束，此时当前要操作的玩家判负（即无法操作的人输）。 假设两人都采用最优策略，问先手是否必胜。 （这其实是一个经典的“取石子”游戏的线性排列版本，但我们可以用区间 DP 的思维分析它。） 第一步：把问题转化为可处理的模型 石子堆从左到右是 stones[ 0] … stones[ n-1 ]。 每次必须从最左边非空堆取任意正整数个（1 到全部）。 取空后该堆消失，下一堆成为新的最左边。 无法操作（即没有石子剩下）的玩家输。 这等价于： 假设当前剩下石子堆的区间是 [ l, r]（0 ≤ l ≤ r < n），先手必须对 stones[ l ] 进行操作： 先手可以从 stones[ l] 中取走 k 个（1 ≤ k ≤ stones[ l ]）。 如果 k = stones[ l]，则剩下 stones[ l] 为空，于是堆区间变成 [ l+1, r ]。 如果 k < stones[ l]，则 stones[ l] 剩下 stones[ l] - k 个石子，堆区间还是 [ l, r ]，但最左边堆的数量变了。 注意 ：当 k < stones[ l ] 时，这堆还在，只是数量减少，所以下次对方仍然必须对这一堆操作，直到它被取完。 于是对于一堆石子来说，如果只剩它自己，那么先手直接全取就赢了。 但如果有后续堆，情况就复杂，因为取的数量会影响后续的胜负。 第二步：定义状态 一种更简洁的转化： 我们可以把每堆的石子数看作一个正整数，游戏的过程是 必须从最左边非空堆取走至少 1 个，然后可以选择取完它（进入下一堆）或不取完（留在本堆） 。 为了方便 DP，我们定义： dp[ l][ r] 表示：石子堆区间是 [ l, r] 时， 当前要操作的玩家 （不一定是原始的先手）是否必胜（True/False）。 初始情况 ： 如果区间为空（l > r），当前玩家没有可取的，必败（False）。 如果区间只有一堆 l==r，那么当前玩家可以一次全取完，取完后对手面对空区间，对手必败，所以当前玩家必胜（True）。 第三步：状态转移 我们要计算 dp[ l][ r ]。 当前玩家必须对 stones[ l] 操作，假设 stones[ l] 剩余 S 个（初始 S = stones[ l ]）。 他可以取走 t 个（1 ≤ t ≤ S）。 取 t 个后，这堆剩下 S - t 个石子。 分两种情况 ： t = S （全取完）： 取完后堆 l 消失，区间变成 [ l+1, r ]。 接下来是对方在 [ l+1, r] 上操作，我们查询 dp[ l+1][ r] 表示 对方在新区间上是否必胜 。 如果 dp[ l+1][ r ] 是 False（对方必败），那么我们这种取法就导致我们胜利（因为对手面对必败局面，我们胜利）。 所以只要存在一种 t = S 使得 dp[ l+1][ r] = False，那么 dp[ l][ r ] = True。 t < S （没取完）： 取完后堆 l 还在，但石子数变成 S - t。 注意：此时区间依然是 [ l, r]，但下一轮是对方操作，而且对方仍然必须对堆 l 操作（因为它没空），但对方面临的局面是 石子数比原来少 的同一个堆。 这相当于：我们先手取走 t 个后，轮到对方在“同一堆数量减少”的情况下操作。这其实可以看作是一个 子游戏 ，但石子数变化，似乎和 l,r 没关系？ 其实我们可以换个思路：这种“没取完”的情况，等价于 先手取走一部分后，交换了先后手角色，但堆还在，所以可以递归到“同一堆数量减少”的同一区间 ？ 不，这里的关键是：当没取完时，堆 l 还是堆 l，只是数量变了，我们可以用另一个维度表示数量，但这样状态太多。 我们可以简化模型： 注意到，对于一堆来说，如果它后面还有堆，那么它的“必胜/必败”不仅仅由它的数量决定，还由后面的堆的胜负决定。 有一个经典技巧：定义 dp[ l] 表示：考虑从 l 到 n-1 这些堆，当前要操作的玩家是否必胜（假设 l 堆数量是 stones[ l ]）。 第四步：一维 DP 解法 设 n 是石子堆数。 定义 dp[ i] 表示： 只考虑从 i 到 n-1 这些堆（且第 i 堆是原数量 stones[ i]），当前要操作的人是否必胜 。 基础情况： 如果没有堆了（i == n），dp[ n ] = False（必败，因为没有石子可取）。 如果 i == n-1（最后一堆），那么当前玩家可以一次全取完，对方没得取，所以 dp[ n-1 ] = True。 对于 i 从 n-2 到 0 计算： 我们面对 stones[ i]，我们必须从它取 1 到 stones[ i ] 个石子。 如果我们可以一次全取完（t = stones[ i ]），那么取完后轮到对方在 i+1 堆开始操作。 即对方面对的局面是 dp[ i+1 ]。 如果 dp[ i+1] 是 False，说明对方必败，那么我们这种操作就赢，所以 dp[ i ] 可能为 True。 如果我们不一次全取完（t < stones[ i]），那么取 t 个后，第 i 堆还剩 stones[ i ] - t 个石子，仍然在位置 i，轮到对方操作。 但此时对方的局面是： 同一堆 i 数量减少 。 注意，对于对方来说，此时他面对的是 相同索引 i 但石子数更少 的情况，这实际上等价于一个新的游戏，起始就是 stones[ i]-t 个石子在堆 i，后面是 stones[ i+1]…stones[ n-1 ]。 也就是说，如果定义 f(s, i) 为“堆 i 当前数量为 s，后面堆是 stones[ i+1]…stones[ n-1]，当前要操作的人是否必胜”，那么我们的 DP 可以扩展到二维 s 和 i，但 s 最大是 stones[ i ]，状态数总和是 O(sum(stones) + n)，可能很大。 但是，这里有一个经典结论（Nim 的变形）： 当面对一堆石子数量 s 且后面有其它堆时，当前玩家可以取 1 到 s 个，如果取完后剩下 s' 个（s'>=0），那么 ： 如果 s'=0，则交给对方在 i+1 堆开始； 如果 s'>0，则交给对方在同一堆 i 但数量为 s' 的局面。 所以我们用二维 dp[ i][ s] 表示“从第 i 堆开始，且第 i 堆当前石子数为 s（1 ≤ s ≤ stones[ i ]），当前玩家是否必胜”。 初始化： dp[ i][ 0] 表示第 i 堆已空，所以等价于 dp[ i+1][ stones[ i+1] ]（即从下一堆原数量开始）。 为了方便，定义 win(i) = dp[ i][ stones[ i] ] 表示第 i 堆是原数量时的胜负。 计算 dp[ i][ s]（s 从 1 到 stones[ i ]）： 当前玩家可以取 1 到 s 个石子，取 k 个后剩下 s-k 个： 如果 s-k = 0，则轮到对方在 i+1 堆原数量开始，即局面是 win(i+1)。 如果 s-k > 0，则轮到对方在 dp[ i][ s-k ] 的局面。 于是： dp[ i][ s] = True 当且仅当 存在 k ∈ {1,…,s} 使得 ： 若 s-k==0，则 win(i+1) = False； 若 s-k>0，则 dp[ i][ s-k ] = False。 这个递推可以从 s 从小到大计算，因为 dp[ i][ s-k ] 的 s-k 更小。 第五步：简化递推 从上述规则发现，dp[ i][ s] 只和 dp[ i][ 小于s的数 ] 以及 win(i+1) 有关。 我们可以计算 win(i) = dp[ i][ stones[ i] ]。 推导边界： 对于最后一堆 i = n-1： 无论 s 是多少，如果 s>0，当前玩家全取完（k=s），则对方在 i+1=n 堆（空）必败，所以当前必胜。 所以 dp[ n-1][ s ] = True 对所有 s≥1。 特别地，win(n-1) = True。 对于 i < n-1： 我们计算 dp[ i][ 1 ]： s=1，只能取 k=1，取完 s-k=0，所以局面交给 win(i+1)。 所以 dp[ i][ 1 ] = True 当且仅当 win(i+1) = False。 然后 s=2 时，可取的 k=1 或 2： 取 1 剩 1 -> 对方 dp[ i][ 1 ] 取 2 剩 0 -> 对方 win(i+1) 所以 dp[ i][ 2] = True 当且仅当 (dp[ i][ 1 ] = False) 或 (win(i+1) = False) 至少一个成立。 推广： dp[ i][ s ] = not ( 所有可能的下一步都是对手的必胜局面 )。 下一步的可能是： 对手局面集合 = { dp[ i][ s-1], dp[ i][ s-2], …, dp[ i][ 0?] 注意 dp[ i][ 0 ] 就是 win(i+1) } 中对应 k=1..s 的那些。 更简单的规律： 定义 mex 为最小的非负整数不在集合中，但这里是布尔值，其实就是看是否存在一个 k 使得对手局面是必败。 其实可以发现，对于固定 i，dp[ i][ s] 的值随着 s 增加，会出现 周期为 2 的模式 ，如果 win(i+1)=True 则 dp[ i][ 奇数]=False, dp[ i][ 偶数 ]=True 之类的。但我们可以直接递推。 第六步：直接计算 win(i) 的递推 我们可以发现，其实不需要所有 s，只需要知道 win(i) 即可。 观察： dp[ i][ s] 的值只取决于 win(i+1) 和 dp[ i][ 1…s-1 ]。 可以计算几个例子找规律，但已知结论（来自取石子游戏“取火柴”单堆但必须取至少1个，但这里后面还有堆）是： 定理 ： 定义 g[ i ] = win(i)（True/False）。 那么： g[ n ] = False（没有堆，必败）。 g[ i ] 的计算： 我们看从 stones[ i ] 开始，可以转移到： 全取完 → 对方局面 g[ i+1 ]。 取一部分剩 s' (1 ≤ s' < stones[ i]) → 对方局面 dp[ i][ s' ]。 而 dp[ i][ s'] 的计算依赖更小的 s'，我们可以从 s=1 往上推出 dp[ i][* ]，然后得到 g[ i ]。 但更简单结论（经推导可得）： g[ i] = True 当且仅当 (stones[ i] > 1) 或 (stones[ i] == 1 且 g[ i+1 ] = False)。 举例验证： n=1, stones=[ 1]: g[ 1]不存在，g[ 0]：stones[ 0]=1，g[ 1]=False → g[ 0 ]=True。正确，因为先手一次取完就赢。 n=2, stones=[ 1,1]: g[ 2]=False, g[ 1]: stones[ 1]=1 且 g[ 2]=False → g[ 1 ]=True。 g[ 0]: stones[ 0]=1 且 g[ 1]=True → g[ 0]=False。正确，因为[ 1,1 ]先手必败。 但这是错的，我们实际模拟 [ 1,1 ]： 先手取第一堆 1 个，第一堆空，后手面对 [ 1]，后手取完胜，先手输，所以 g[ 0 ]=False 对。 但公式 stones[ i]>1 时 g[ i ]=True 吗？ 看 [ 2,1 ]： g[ 2]=False（最后一堆[ 1]必胜），g[ 1]: stones[ 1]=1 且 g[ 2]=False → g[ 1 ]=True。 g[ 0]: stones[ 0]=2 (>1) → g[ 0]=True。验证：先手面对[ 2,1]，可以取第一堆 1 个剩 1 个，对方面对[ 1,1]，上面已知[ 1,1 ]先手败，所以对方败，我们胜。是的。 看来公式是： g[ i] = (stones[ i] > 1) 或者 (stones[ i] == 1 且 g[ i+1 ] == False)。 即：如果 stones[ i] 是 1，则 g[ i] = not g[ i+1]；如果 stones[ i] > 1，则 g[ i ] = True。 验证 [ 1,2 ]： g[ 2] 最后一堆[ 2]，g[ 2 ]=True（因为>1）。 g[ 1]: stones[ 1 ]=2>1 → True。 g[ 0]: stones[ 0]=1 且 g[ 1]=True → g[ 0 ]=False。 模拟：先手面对[ 1,2]，只能取第一堆 1 个，剩下[ 2 ]，后手一次取完胜，先手败，对。 第七步：最终算法 这样我们得到一个 O(n) 算法： 初始化 g[ n ] = False。 从 i = n-1 到 0： 如果 stones[ i] > 1，g[ i ] = True。 如果 stones[ i] == 1，g[ i] = not g[ i+1 ]。 答案就是 g[ 0 ]。 为什么 stones[ i ] > 1 时必胜？ 因为先手可以控制： 如果 g[ i+1] = True（对方在下一堆先手必胜），那么我们可以不一次取完 stones[ i]，只取 stones[ i]-1 个，剩 1 个给对方，这样对方必须取这最后 1 个，取完后轮到我们在下一堆先手（即 g[ i+1] 的局面），但 g[ i+1 ] 表示下一堆当前玩家（现在是对方）必胜，但对方取完 1 个后，下一堆的当前玩家变成我们，所以我们是那个“必胜”的玩家。 这里需要小心角色交换，其实推导结果是：剩 1 个给对方，对方取完后，我们变成下一堆的先手，而 g[ i+1 ]=True 表示下一堆的先手必胜，所以我们必胜。 如果 g[ i+1] = False，那更简单，我们直接全取完 stones[ i ]，让对方在下一堆先手并面对必败局面，我们就赢了。 所以无论如何 stones[ i ]>1 时先手必胜。 stones[ i]==1 时，我们只能取完，所以局面完全交给 g[ i+1] 的对手，所以 g[ i] = not g[ i+1 ]。 第八步：例子验证 例：stones = [ 1,1,2 ] n=3 g[ 3 ]=False i=2: stones[ 2]=2>1 → g[ 2 ]=True i=1: stones[ 1]=1 → g[ 1] = not g[ 2 ] = False i=0: stones[ 0]=1 → g[ 0] = not g[ 1 ] = True 所以先手必胜。 模拟： 先手面对[ 1,1,2]，先手取第一堆 1 个→剩[ 1,2 ]给后手。 后手面对[ 1,2]，后手必须取第一堆 1 个→剩[ 2 ]给先手。 先手面对[ 2 ]，取 2 个完胜。先手胜，符合。 这样我们就用一维 DP 和博弈推导解决了这个“必须取最左边堆”的取石子游戏。