292. Nim Game

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.

Example:

Input: 4 Output: false  Explanation: 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. 292. Nim Game 

---

博弈论的题。两个人轮流拿石头，一次可以拿1~3个，拿掉最后一个石头的人获胜。规定我先拿，问如果石头数为n时，我是否可以取胜。 看Hint，找规律。

• 如果n∈[1,3]，则我第一次拿就可以把所有石头拿走，所以我肯定可以获胜。
• 如果n=4，则无论我第一次拿多少个，因为我最多可以拿3个，所以剩下的石头数转换为了n∈[1,3]的情况，也就是变成了对手肯定能获胜的情况。
• 如果n∈[5,7]，则我为了获胜，可以想方设法让我第一次拿了之后，剩余4个石头，这样相当于对手遇到n=4的情况，于是转换为我可以获胜的情况。
• 如果n=8，则无论第一次拿多少个，剩余的石头个数都转换为了n∈[5,7]的情况，也就变成了对手必胜的情况。
• …

观察以上的分析，发现当n是4的倍数时，我必输；否则我必胜。代码就很好写了：

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

本代码提交AC，用时0MS。
类似博弈论的题，一定要在纸上写几个例子出来，然后仔细找规律。