1510-石子游戏 IV

Raphael Liu Lv10
  2023-09-13 00:47:26 2023-09-13 00:47:26 Created   2023-09-13 16:06:23 2023-09-13 16:06:23 Updated    

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

方法一：动态规划

我们用 f[i] 表示先手在面对 i 颗石子时是否处于必胜态（会赢得比赛）。由于先手和后手都采取最优策略，那么 f[i] 为必胜态，当且仅当存在某个 f[i - k^2] 为必败态。也就是说，当先手在面对 i 颗石子时，可以选择取走 k^2 颗，剩余的 i-k^2 颗对于后手来说是必败态，因此先手会获胜。

我们可以写出状态转移方程：

f[i] = \begin{cases}
\text{true}, & \text{any} f[i-k^2] \text{is false where~} 1 \leq k^2 \leq i \
\text{false}, & \text{otherwise}
\end{cases}

边界条件为 f[0]=\text{false，即没有石子时，先手会输掉游戏。

最终的答案即为 f[n]。

[sol1-C++]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<int> f(n + 1);
        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k * k <= i; ++k) {
                if (!f[i - k * k]) {
                    f[i] = true;
                    break;
                }
            }
        }
        
        return f[n];
    }
};
[sol1-Java]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean winnerSquareGame(int n) {
        boolean[] f = new boolean[n + 1];
        for (int i = 1; i <= n; ++i) {
            for (int k = 1; k * k <= i; ++k) {
                if (!f[i - k * k]) {
                    f[i] = true;
                    break;
                }
            }
        }
        
        return f[n];
    }
}
[sol1-Python3]
1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        f = [False] * (n + 1)
        for i in range(1, n + 1):
            k = 1
            while k * k <= i:
                if not f[i - k * k]:
                    f[i] = True
                    break
                k += 1
        
        return f[n]
[sol1-C]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
bool winnerSquareGame(int n) {
    int f[n + 1];
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) {
        for (int k = 1; k * k <= i; ++k) {
            if (!f[i - k * k]) {
                f[i] = true;
                break;
            }
        }
    }

    return f[n];
}

复杂度分析

  • 时间复杂度：O(n \sqrt n)。对于每一个数 i，k 的枚举上限不超过 \sqrt i，所以总时间复杂度为 O(\sum_{i=1}^n \sqrt i) = O(n \sqrt n)。

  • 空间复杂度：O(n)，即为存储所有状态需要的空间。

 Comments
On this page
1510-石子游戏 IV