【博弈论】简单博弈论入门题

题目描述

这是 LeetCode 上的 292. Nim 游戏 ，难度为 简单。

Tag : 「博弈论」

你和你的朋友，两个人一起玩 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−11 <= n <= 2^{31} - 11<=n<=231−1

博弈论

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

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

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

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

...

到这里，我们猜想 当起始局面石子数量为 4 的倍数，则先手必败，否则先手必胜（即 n % 4 != 0 时，先手必胜）。

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

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

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

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

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

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

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

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

代码：

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

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

最后

这是我们「刷穿 LeetCode」系列文章的第 No.292 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉