LeetCode 292. Nim Game(博弈论)

题目

题意：地上有一堆石头，每次只能拿1-3个石头，两个人轮流拿，谁拿走最后一个石头，谁就获胜。你先手。

题解：如果地上的石头小于等于3个，先手必赢，当等于4的时候，后手必赢。基于4我们可以推出，当石头的数=8的时候，后手也必赢，5，6，7都是先手赢，所以规律可以递推找到，就是看是否是4的整数倍。
两外注意石头数为0的时候

class Solution {
public:
    bool canWinNim(int n) {
        if(n==0)
            return false;
        
        if(n%4==0)
            return false;
        return true;
    }
};