1510. Stone Game IV =================== 题目信息 -------- :题号: 1510 :难度: Hard :主题: 博弈论、动态规划、完全平方数 :原题: `LeetCode 1510 `_ :重点: 两人轮流移除正完全平方数颗石子,无法行动者失败;判断先手在双方最优策略下能否获胜 题目重述 -------- 一堆中初始有 ``n`` 颗石子。Alice 与 Bob 轮流行动,Alice 先手。每次必须移除 ``x^2`` 颗石子,其中 ``x`` 为正整数且移除数量不能超过当前剩余石子数。 无法进行合法操作的玩家失败。假设双方都采用最优策略,请判断 Alice 是否必胜。 ``1 <= n <= 10^5``。 自建示例 -------- 先手唯一选择会把必胜状态交给对手: .. code-block:: text 输入:n = 2 输出:false 解释:Alice 只能移除一颗,Bob 随后移除最后一颗并获胜。 石子数本身是完全平方数时先手可立即取完: .. code-block:: text 输入:n = 1 输出:true 解释:Alice 移除 1^2 颗石子后,Bob 无法行动。