Sign in Subscribe
算法

石子游戏 IV

loser

• 8 min read
Share

Alice 和 Bob 两个人轮流玩一个游戏，Alice 先手。

一开始，有 n 个石子堆在一起。每个人轮流操作，正在操作的玩家可以从石子堆里拿走 任意 非零 平方数 个石子。

如果石子堆里没有石子了，则无法操作的玩家输掉游戏。

给你正整数 n ，且已知两个人都采取最优策略。如果 Alice 会赢得比赛，那么返回 True ，否则返回 False 。

示例 1：

输入：n = 1
输出：true
解释：Alice 拿走 1 个石子并赢得胜利，因为 Bob 无法进行任何操作。

示例 2：

输入：n = 2
输出：false
解释：Alice 只能拿走 1 个石子，然后 Bob 拿走最后一个石子并赢得胜利（2 -> 1 -> 0）。

示例 3：

输入：n = 4
输出：true
解释：n 已经是一个平方数，Alice 可以一次全拿掉 4 个石子并赢得胜利（4 -> 0）。

示例 4：

输入：n = 7
输出：false
解释：当 Bob 采取最优策略时，Alice 无法赢得比赛。
如果 Alice 一开始拿走 4 个石子， Bob 会拿走 1 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 3 -> 2 -> 1 -> 0）。
如果 Alice 一开始拿走 1 个石子， Bob 会拿走 4 个石子，然后 Alice 只能拿走 1 个石子，Bob 拿走最后一个石子并赢得胜利（7 -> 6 -> 2 -> 1 -> 0）。

示例 5：

输入：n = 17
输出：false
解释：如果 Bob 采取最优策略，Alice 无法赢得胜利。

提示：

  • 1 <= n <= 10^5

动态规划：

class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<bool> dp(n + 1, false);
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j * j <= i; j++)
            {
                int sq = j * j;
                if (dp[i - sq] == false)
                {
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[n];
    }
};

核心思想

这题和前面的石子游戏 II、石子游戏 III 有一点不一样。

前两题更像是在比较“谁能拿到更多分数”，所以经常会用“当前玩家最多能拿多少”或者“当前玩家和对手的最大分差”来做状态。

但这道题只问：

Alice 最后能不能赢。

也就是说，我们不需要关心 Alice 能拿多少石子，也不需要关心 Bob 能拿多少石子，只需要判断某个局面是 必胜态 还是 必败态。

所以可以定义：

  • dp[i] = true：表示当前轮到某个玩家操作，并且还剩 i 个石子时，当前玩家必胜。
  • dp[i] = false：表示当前轮到某个玩家操作，并且还剩 i 个石子时，当前玩家必败。

注意，这里的“当前玩家”不一定是 Alice。

因为游戏轮流进行，所以当 Alice 拿完以后，剩下的状态就是 Bob 作为“当前玩家”的状态。
我们只要知道“轮到当前玩家时，这个状态是赢还是输”即可。

状态转移

当还剩 i 个石子时，当前玩家可以拿走任意非零平方数个石子。

也就是可以拿：

1^2, 2^2, 3^2, ..., j^2

其中：

j * j <= i

如果当前玩家拿走 j * j 个石子，那么剩余石子数变成：

i - j * j

接下来就轮到对手操作。

于是问题变成：

有没有一种拿法，能让对手进入必败态？

如果存在某个平方数 j * j，使得：

dp[i - j * j] == false

说明当前玩家拿走 j * j 个石子后，对手面对的是一个必败局面。

那么当前玩家就可以选择这个拿法，从而保证自己获胜。

所以：

dp[i] = true

反过来，如果所有合法的平方数都试过以后，剩下的状态全都是对手的必胜态，也就是：

dp[i - j * j] == true

那么无论当前玩家怎么拿，对手都能赢。

所以：

dp[i] = false

因此状态转移公式就是：

dp[i] = 存在 j，使得 j * j <= i 且 dp[i - j * j] == false

写成代码就是：

for (int j = 1; j * j <= i; j++)
{
    int sq = j * j;
    if (dp[i - sq] == false)
    {
        dp[i] = true;
        break;
    }
}

边界情况

最基础的状态是：

dp[0] = false

因为如果轮到某个玩家操作时，已经没有石子了，那么这个玩家无法操作，直接输掉游戏。

所以还剩 0 个石子时，是当前玩家的必败态。

代码中：

vector<bool> dp(n + 1, false);

默认就把 dp[0] 初始化成了 false。

然后从 1 开始递推到 n。

为什么从小到大递推

计算 dp[i] 时，我们需要知道：

dp[i - 1^2]

dp[i - 2^2]

dp[i - 3^2]

这些状态。

它们的剩余石子数都小于 i。

所以只要我们从 1 一直递推到 n，在计算 dp[i] 的时候，所有可能用到的子状态都已经算好了。

这就是动态规划成立的顺序。

公式为什么正确

这道题的关键逻辑可以总结成一句话：

当前状态是必胜态，当且仅当它能一步走到某个必败态。

下面分两边证明。

1. 如果能走到必败态，那么当前状态必胜

假设存在一个平方数 sq，使得：

dp[i - sq] == false

这表示当前玩家拿走 sq 个石子之后，对手会面对一个必败状态。

由于双方都采取最优策略，当前玩家一定会选择这个 sq。

这样对手无论怎么操作，最终都会输。

所以当前状态 dp[i] 一定是必胜态。

2. 如果走不到必败态，那么当前状态必败

如果对于所有合法平方数 sq，都有：

dp[i - sq] == true

说明当前玩家不管拿多少平方数个石子，都会把对手送进必胜态。

对手同样采取最优策略，所以对手一定能赢。

因此当前玩家没有任何获胜方式，dp[i] 必然是必败态。

这两个方向合起来，就证明了转移公式：

dp[i] = 存在 sq，使得 dp[i - sq] == false

正确性证明

我们用数学归纳法证明：对于所有 0 <= i <= n，dp[i] 都正确表示“还剩 i 个石子，轮到当前玩家时，当前玩家是否必胜”。

归纳基

当 i = 0 时，当前玩家没有石子可以拿，无法操作。

根据题意，无法操作的玩家输。

所以 dp[0] = false 正确。

归纳假设

假设对于所有 0 <= k < i，dp[k] 都已经正确表示对应状态的胜负。

归纳推导

现在考虑 dp[i]。

当前玩家可以选择任意平方数 sq = j * j，其中 sq <= i。

每一种选择都会把游戏带到一个更小的状态：

i - sq

由于 i - sq < i，根据归纳假设，dp[i - sq] 的胜负结果是正确的。

如果存在某个 sq，使得 dp[i - sq] == false，说明当前玩家可以一步把对手送入必败态，因此当前玩家必胜。

如果不存在这样的 sq，说明当前玩家所有选择都会让对手进入必胜态，因此当前玩家必败。

这正好和代码中的转移逻辑完全一致。

所以 dp[i] 正确。

由数学归纳法可知，最终 dp[n] 正确。

举例理解

以较小的几个状态为例：

  • dp[0] = false：没有石子，当前玩家输
  • dp[1] = true：拿走 1 个，剩下 0，对手输
  • dp[2] = false：只能拿 1 个，剩下 1，对手赢
  • dp[3] = true：拿走 1 个，剩下 2，对手输
  • dp[4] = true：直接拿走 4 个，剩下 0，对手输

再看 n = 7：

  • 拿 1 个，剩 6
  • 拿 4 个，剩 3

如果 dp[6] 和 dp[3] 都是 true，说明无论 Alice 怎么拿，Bob 都会进入必胜态。

所以 dp[7] = false。

这和示例 4 一致。

复杂度分析

外层循环枚举剩余石子数：

i = 1 ... n

内层循环枚举可以拿走的平方数：

1^2, 2^2, ..., j^2 <= i

也就是最多枚举 sqrt(i) 次。

所以总时间复杂度为：

O(n * sqrt(n))

额外使用了一个长度为 n + 1 的 dp 数组，所以空间复杂度为：

O(n)

在题目范围 n <= 10^5 下，这个复杂度可以通过。