Nim Game

今天来讲一下目前LeetCode OJ上通过率第二高的题。题目如下：

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

题目大意就是要判断是否能赢得游戏在给定石头数量的条件下。当时一看到题目，心想，这不是很简单嘛，我能不能赢，不就相当于我拿走1～3颗石子后，对方会不会输嘛。只要对方有一种可能输，我就采取相应的策略就能赢了啊。所以，随性的代码如下：

class Solution {
public:
    bool canWinNim(int n) {
        if(n == 1 || n == 2 || n == 3)
            return true;
        else
            return !canWinNim(n - 3) || !canWinNim(n - 2) || !canWinNim(n - 1);
    }
};

很不幸，提交上去直接Runtime Error了。一想，递归的子过程有公共的交集，应该用动态规划的手段来解决，于是改进的方案如下：

class Solution {
public:
    bool canWinNim(int n) {
        bool *result = new bool[4];
        if(n == 1 || n == 2 || n == 3)
            return true;
        else {
            result[1] = true;
            result[2] = true;
            result[3] = true;
            for(int i = 4; i <= n; i++) {
                result[0] = !result[3] || !result[2] || !result[1];
                result[1] = result[2];
                result[2] = result[3];
                result[3] = result[0];
            }
            return result[0];
        }
    }
};

因为n颗石子的结果取决于少1～3颗石子的结果，所以我们需要4个空间即可完成任务。然而，提交上去之后就超时了。>.<

然后就懵逼了。于是偷窥了一下hint：

If there are 5 stones in the heap, could you figure out a way to remove the stones such that you will always be the winner?

这个提示强烈地暗示了这道题目是有规律的。于是，画了画草图，发现当石子数量为1，2，3时必胜，4时必输。如果数量为5，那先取1颗石子，然后剩下4颗，这样对方必输。如此递推，我们可以得到一个规律：当石子数量为4的倍数时，必输；否则，必胜。于是关键代码就只有一行了。。。

class Solution {
public:
    bool canWinNim(int n) {
        return n & 3;
    }
};

这里，%4运算可以用&3来代替，因为%4就是取一个数二进制表示的最末两位。