石子游戏 IV

难度: Hard

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

Submission

运行时间: 121 ms

内存: 19.9 MB

class Solution:
    def winnerSquareGame(self, n: int) -> bool:

        @cache
        def dfs(x):
            if not x :return False
            for i in range(isqrt(x),0,-1):
                if not dfs(x-i**2):
                    return True 
            return False
        return dfs(n)

Explain

题解采用了记忆化搜索（动态规划的一种形式），其核心思想是递归地解决子问题，并缓存中间结果以避免重复计算。在每一步，Alice尝试拿走所有可能的平方数数量的石子。对于每一种可能的移动，Alice会检查剩余石子数量是否会导致对手Bob输掉游戏。如果存在任何一种移动使得Bob处于必败状态（即Bob无法通过任何方式赢得游戏），那么Alice就处于必胜状态。通过递归检查每一种可能的游戏状态，我们可以确定Alice是否有必胜的策略。

时间复杂度: O(n * sqrt(n))

空间复杂度: O(n)

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        from functools import cache
        from math import isqrt

        @cache
        def dfs(x):
            # 如果没有石子剩余，当前玩家输掉游戏
            if not x :return False
            # 逐一尝试所有可能的平方数拿法
            for i in range(isqrt(x), 0, -1):
                # 如果对手处于输的状态，则当前玩家赢
                if not dfs(x - i**2):
                    return True
            # 如果所有移动都不能使对手输，当前玩家输
            return False
        return dfs(n)

Explore

从最大的平方数开始尝试可以更快地减少问题规模，因为这样可以立即减掉更多的石子。在某些情况下，这可能更快地到达决策点，尤其是在可能存在较大平方数的解决方案时。此外，从大到小尝试有可能在遇到第一个使对手处于必败状态的策略时立即停止搜索，从而提高算法效率。

记忆化搜索通过使用缓存来存储已经计算过的游戏状态的结果。在Python中，这可以通过使用functools模块中的`cache`装饰器实现。这个装饰器自动记录每个函数调用的参数和相应的结果。如果函数再次用相同的参数调用，它会直接返回缓存中的结果，而不是重新计算。这样，每个游戏状态只计算一次，大大提高了效率。

在递归深度过大可能导致栈溢出的情况下，可以考虑使用迭代的方式代替递归，或者使用尾递归优化。在Python中，尾递归优化并不是由语言自动处理的，因此通常推荐使用迭代的动态规划方法。例如，可以通过构建一个动态规划表从底向上计算，避免递归调用，从而解决栈溢出问题。

算法通过递归检查所有可能的平方数移动来确保考虑了所有可能的策略。对于每一种可能的石子数量减少方式（即选择任意一个平方数），算法都计算剩余石子数量对于对手的影响。通过这种方式，可以确保Alice如果有任何一种方式使对手处于必败状态，则算法会发现并返回Alice为必胜。这种全面的搜索确保了不会遗漏任何可能的胜利策略。