题解 | #Nim游戏#

题目的主要信息：

这是一个经典的博弈。 你和你的朋友，两个人玩一个游戏。

1. 桌子上有 n 个石头
2. 你和你的朋友轮流取石头，你先手。
3. 每一回合可以取 1~3 个石头。
4. 轮到你的朋友时桌上没有石头则你获胜，否则你的朋友获胜。

你和你的朋友都尽力让自己获胜，如果你有方法必胜，则返回 true ，如果你的朋友有方法必胜，则返回 false

方法一：

采用递归（超时）。遍历三种情况，即取1个、取2个、取3个，然后再递归计算朋友的情况$f(n-1)\mathrm{、}f(n-2)\mathrm{、}f(n-3)f(n-1)、f(n-2)、f(n-3)$，如果朋友失败，则我们获胜。如果无论我们取多少个，朋友都成功，则我们失败。

具体做法：

class Solution {
public:
    bool NimGame(int n) {
        if(n <= 3){//我们可以直接取走，获胜
            return true;
        }
        for(int i = 1;i <= 3;i++){//遍历三种情况，每次取i个
            //递归计算朋友的情况
            if(NimGame(n-i)==false) {// 只要朋友失败，我们就获胜
                return true;
            }
        }
        //如果朋友成功，则我们失败
        return false; 
    }
};

复杂度分析：

• 时间复杂度：$O(3^n)O(3^n)$，总共有三种情况，每次都要递归。
• 空间复杂度：$O(n)O(n)$，递归栈大小为n。

方法二：

直接判断。如果桌上有1-3个石头，我们都能全部取走，我们必胜；如果桌上有4个石头，无论我们取多少，轮到朋友的时候他都能全部取走，朋友必胜。因此，可以归纳推理到，如果桌上有$4i(i=1,2,3\dots \dots )4i(i=1,2,3\dots \dots )$个石头，则朋友必胜，否则我们获胜。

具体做法：

class Solution {
public:

    bool NimGame(int n) {
        if ( n % 4 == 0) {//若是4的倍数，则朋友必胜
            return false;
        }else {//非4的倍数
            return true;
        }
    }
};

复杂度分析：

• 时间复杂度：$O(1)O(1)$，直接判断。
• 空间复杂度：$O(1)O(1)$，只用了常数空间。