1510. 石子游戏 IV

题目描述

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

解法

方法一：记忆化搜索

我们设计一个函数 \(dfs(i)\)，表示当前石子堆中有 \(i\) 个石子时，当前玩家是否能赢得比赛。如果当前玩家能赢得比赛，则返回 \(true\)，否则返回 \(false\)。那么答案即为 \(dfs(n)\)。

函数 \(dfs(i)\) 的计算过程如下：

如果 \(i \leq 0\)，说明当前玩家无法进行任何操作，因此当前玩家输掉比赛，返回 \(false\)；
否则，枚举当前玩家可以拿走的石子数量 \(j\)，其中 \(j\) 为平方数，如果当前玩家拿走 \(j\) 个石子后，另一个玩家无法赢得比赛，则当前玩家赢得比赛，返回 \(true\)。如果枚举完所有的 \(j\)，都无法满足上述条件，则当前玩家输掉比赛，返回 \(false\)。

为了避免重复计算，我们可以使用记忆化搜索，即使用数组 \(f\) 记录函数 \(dfs(i)\) 的计算结果。

时间复杂度 \(O(n \times \sqrt{n})\)，空间复杂度 \(O(n)\)。其中 \(n\) 为石子堆中石子的数量。

Python3JavaC++GoTypeScript

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        @cache
        def dfs(i: int) -> bool:
            if i == 0:
                return False
            j = 1
            while j * j <= i:
                if not dfs(i - j * j):
                    return True
                j += 1
            return False

        return dfs(n)

class Solution {
    private Boolean[] f;

    public boolean winnerSquareGame(int n) {
        f = new Boolean[n + 1];
        return dfs(n);
    }

    private boolean dfs(int i) {
        if (i <= 0) {
            return false;
        }
        if (f[i] != null) {
            return f[i];
        }
        for (int j = 1; j <= i / j; ++j) {
            if (!dfs(i - j * j)) {
                return f[i] = true;
            }
        }
        return f[i] = false;
    }
}

class Solution {
public:
    bool winnerSquareGame(int n) {
        int f[n + 1];
        memset(f, 0, sizeof(f));
        function<bool(int)> dfs = [&](int i) -> bool {
            if (i <= 0) {
                return false;
            }
            if (f[i] != 0) {
                return f[i] == 1;
            }
            for (int j = 1; j <= i / j; ++j) {
                if (!dfs(i - j * j)) {
                    f[i] = 1;
                    return true;
                }
            }
            f[i] = -1;
            return false;
        };
        return dfs(n);
    }
};

func winnerSquareGame(n int) bool {
    f := make([]int, n+1)
    var dfs func(int) bool
    dfs = func(i int) bool {
        if i <= 0 {
            return false
        }
        if f[i] != 0 {
            return f[i] == 1
        }
        for j := 1; j <= i/j; j++ {
            if !dfs(i - j*j) {
                f[i] = 1
                return true
            }
        }
        f[i] = -1
        return false
    }
    return dfs(n)
}

function winnerSquareGame(n: number): boolean {
    const f: number[] = new Array(n + 1).fill(0);
    const dfs = (i: number): boolean => {
        if (i <= 0) {
            return false;
        }
        if (f[i] !== 0) {
            return f[i] === 1;
        }
        for (let j = 1; j * j <= i; ++j) {
            if (!dfs(i - j * j)) {
                f[i] = 1;
                return true;
            }
        }
        f[i] = -1;
        return false;
    };
    return dfs(n);
}

方法二：动态规划

我们也可以使用动态规划求解本题。

定义数组 \(f\)，其中 \(f[i]\) 表示当前石子堆中有 \(i\) 个石子时，当前玩家是否能赢得比赛。如果当前玩家能赢得比赛，则 \(f[i]\) 为 \(true\)，否则为 \(false\)。那么答案即为 \(f[n]\)。

我们在 \([1,..n]\) 的范围内枚举 \(i\)，并在 \([1,..i]\) 的范围内枚举 \(j\)，其中 \(j\) 为平方数，如果当前玩家拿走 \(j\) 个石子后，另一个玩家无法赢得比赛，则当前玩家赢得比赛，即 \(f[i] = true\)。如果枚举完所有的 \(j\)，都无法满足上述条件，则当前玩家输掉比赛，即 \(f[i] = false\)。因此我们可以得到状态转移方程：

\[ f[i]= \begin{cases} true, & \textit{if } \exists j \in [1,..i], j^2 \leq i \textit{ and } f[i-j^2] = false\\ false, & \textit{otherwise} \end{cases} \]

最后，我们返回 \(f[n]\) 即可。