[数据结构与算法]leetcode:292.Nim游戏

题目

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/nim-game

你和你的朋友，两个人一起玩 Nim 游戏：

桌子上有一堆石头。
你们轮流进行自己的回合，你作为先手。
每一回合，轮到的人拿掉 1 - 3 块石头。
拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1：

输入：n = 4
输出：false
解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

示例 2：

输入：n = 1
输出：true

示例 3：

输入：n = 2
输出：true

提示：

1 <= n <= 231 - 1

解法

博弈论
这是一道 Nim 游戏的简化版。

在不知晓博弈论结论前，可以先通过找规律得到猜想，然后再从「何种情况下，先手会处于必胜态」的角度来进行分析。

根据题意，我们尝试从小范围数据的情况进行讨论：

如果落到先手的局面为「石子数量为 1 - 3」的话，那么先手必胜；
如果落到先手的局面为「石子数量为 4」的话，那么先手决策完（无论何种决策），交到后手的局面为「石子数量为 1 - 3」，即此时后手必胜，对应先手必败（到这里我们有一个推论：如果交给先手的局面为 4 的话，那么先手必败）；
如果落到先手的局面为「石子数量为 5 - 7」的话，那么先手可以通过控制选择石子的数量，来使得后手处于「石子数量为 4」的局面（此时后手必败），因此先手必胜；
如果落到先手的局面为「石子数量为 8」的话，由于每次只能选 1 - 3 个石子，因此交由后手的局面为 5 - 7，根据流程 33 我们知道此时先手必败；
…
到这里，我们猜想 当起始局面石子数量为 4 的倍数，则先手必败，否则先手必胜（即 n % 4 != 0 时，先手必胜）。

然后我们通过「归纳法」证明一下该猜想的正确性。

在上面的「找规律」分析中，我们分情况讨论了最后一个决胜回合（我们称「剩余石子数量少于等于 4 的局面」为最后回合）的情况：如果交由先手的石子数量为 4，那么先手必败，否则先手必胜。

而对于「最后回合」前的任意回合（石子数量大于 4），我们需要证明 先手可以通过调整所选石子数量，来维持「n % 4 != 0」直到最后回合。

如果起始对先手而言满足「n % 4 != 0」，此时先手可以通过选择石子数量为「n % 4」来确保交到后手的局面为 4 的倍数。

那么根据推论，此时的原始后手作为下一回合的先手角色，且面临石子数量为 4 的倍数的局面，为必败态。

进一步的解释就是，由于原始后手面临石子数量为 4 的倍数的局面，且只能选 1 - 3 个石子，因此无论如何选择，重新回到原始先手的仍然满足「n % 4 != 0」（非 44 的倍数）。

因此 原始先手只需要确保每次都选择「x % 4」个石子（x 为当前石子数量），就可以确保交由自己的局面一直满足「x % 4 != 0」，交由对方的局面一直满足「x % 4 == 0」，直到最后回合的到来。

至此，我们证明了 如果起始石子数量 n 满足「n % 4 != 0」条件，那么先手必胜。

• python

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0

复杂度分析

• 时间复杂度：O(1)
• 空间复杂度：O(1)