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$ 为石子堆中石子的数量。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
|
方法二:动态规划
我们也可以使用动态规划求解本题。
定义数组 $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]$ 即可。
时间复杂度 $O(n \times \sqrt{n})$,空间复杂度 $O(n)$。其中 $n$ 为石子堆中石子的数量。
1 2 3 4 5 6 7 8 9 10 11 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|
1 2 3 4 5 6 7 8 9 10 11 12 |
|