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块，最后一个取石头的胜利。如果两个人都用最好的策略，问谁可以赢。
自己赢说明上一轮别人肯定不会赢，那么
canWinNim(n) = !canWinNim(n-1) || !canWinNim(n-2) || !canWinNim(n-3);
当数字太大的时候会出现超时， 用dp保存之前的解。

class Solution {
    public boolean canWinNim(int n) {
        if(n<=3) return true;
        boolean dp[] = new boolean[n+1];
        Arrays.fill(dp, 0, 4, true);//fill, not include to
        for(int i=4; i<=n; i++){
            dp[i] = (!dp[i-1]) || (!dp[i-2]) || (!dp[i-3]);
        }
        return dp[n];
    }
}

但是input为1348820612, Memory Limit Exceeded， 于是只需要用3个变量保存即可。
还是会出现超时，看来要用数学来解

class Solution {
    public boolean canWinNim(int n) {
        if(n<=3) return true;
        boolean[] dp = new boolean[3];
        Arrays.fill(dp, true);      
        for(int i=4; i<=n; i++){
            boolean cur = !dp[0] || !dp[1] || !dp[2];
            dp[0] = dp[1];
            dp[1] = dp[2];
            dp[2] = cur;
        }
        return dp[2];
    }
}

数学：如果当前的数字为4， 那么一定会输
如果1* 4 < n < 2 * 4, (n = 5, 6, 7), 会赢，因为我第一把可以把4留给第二个人。然后到了下一个循环。于是能被4整除的数一定会输

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