1510. Stone Game IV

题目信息

题号:

1510

难度:

Hard

主题:

博弈论、动态规划、完全平方数

原题:

LeetCode 1510

重点:

两人轮流移除正完全平方数颗石子,无法行动者失败;判断先手在双方最优策略下能否获胜

题目重述

一堆中初始有 n 颗石子。Alice 与 Bob 轮流行动,Alice 先手。每次必须移除 x^2 颗石子,其中 x 为正整数且移除数量不能超过当前剩余石子数。

无法进行合法操作的玩家失败。假设双方都采用最优策略,请判断 Alice 是否必胜。

1 <= n <= 10^5。

自建示例

先手唯一选择会把必胜状态交给对手:

输入:n = 2
输出:false
解释:Alice 只能移除一颗,Bob 随后移除最后一颗并获胜。

石子数本身是完全平方数时先手可立即取完:

输入:n = 1
输出:true
解释:Alice 移除 1^2 颗石子后,Bob 无法行动。