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)。

约束条件：

  • 1 <= n <= 10^5

解题思路

这是一个典型的博弈论动态规划问题。我们需要判断在当前状态下，当前玩家是否能够获胜。

核心思路：

  1. 定义状态：dp[i] 表示当剩余 i 个石子时，当前玩家是否能获胜
  2. 状态转移：对于当前的 i 个石子，玩家可以选择移除任意完全平方数个石子（1², 2², 3², …）
  3. 如果存在一种移动方式，使得对手处于必败状态，那么当前玩家就能获胜
  4. 即：dp[i] = true 当且仅当存在某个完全平方数 j²，使得 dp[i - j²] = false

算法步骤：

  • 初始化：dp[0] = false（没有石子时当前玩家败）
  • 对于每个 i 从 1 到 n，尝试所有可能的完全平方数移动
  • 如果存在一种移动使得对手败，则当前玩家胜

优化： 可以预计算所有需要的完全平方数，避免重复计算平方根。

时间复杂度为 O(n * √n)，空间复杂度为 O(n)。

代码实现

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++) {
                if (!dp[i - j * j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
};

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        dp = [False] * (n + 1)
        
        for i in range(1, n + 1):
            j = 1
            while j * j <= i:
                if not dp[i - j * j]:
                    dp[i] = True
                    break
                j += 1
        
        return dp[n]

public class Solution {
    public bool WinnerSquareGame(int n) {
        bool[] dp = new bool[n + 1];
        
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                if (!dp[i - j * j]) {
                    dp[i] = true;
                    break;
                }
            }
        }
        
        return dp[n];
    }
}

var winnerSquareGame = function(n) {
    const dp = new Array(n + 1).fill(false);
    
    for (let i = 1; i <= n; i++) {
        for (let j = 1; j * j <= i; j++) {
            if (!dp[i - j * j]) {
                dp[i] = true;
                break;
            }
        }
    }
    
    return dp[n];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值
时间复杂度O(n × √n)
空间复杂度O(n)

相关题目