394. 硬币排成线

描述

有 n 个硬币排成一条线。两个参赛者轮流从右边依次拿走 1 或 2 个硬币，直到没有硬币为止。拿到最后一枚硬币的人获胜。
请判定 第一个玩家 是输还是赢？

样例

n = 1, 返回 true.
n = 2, 返回 true.
n = 3, 返回 false.
n = 4, 返回 true.
n = 5, 返回 true.

挑战

O(1) 时间复杂度且O(1) 存储。

代码

1. 当前硬币 1 个或者 2 个第一个人一次取走胜利，当前硬币 3 个第一个人无论怎么取第二个人都胜利。 最简单的做法是如果硬币个数是不是 3 的倍数，那第一个人第一次取走 n%3 个硬币，使剩下的硬币数目变成 3 的倍数，之后只需保证在第二个人取完后，第一个人根据第二个人取的硬币使得剩下硬币数目被 3 整除即可

public class Solution {
    /**
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int n) {
        return n % 3 != 0;
    }
}

2. 动态规划
   思路
   设置 buff[i] 为：有i个硬币的时候第一个玩家是赢还是输。
3. 如果 buff[i-1] 和 buff[i-2] 都是赢，那我一开始无论取 1 个还是 2 个，对方都可以赢。（我取完之后可以看做对方是先手）
4. 如果 buff[i-1] 是赢，buff[i-2] 是输，那我一开始就取 2 个，对方剩下 i-2 个只能输。那就是我可以赢。
5. 如果 buff[i-2] 是赢，buff[i-1] 是输，那我一开始就取 1 个，对方剩下 i-1个只能输。那就是我可以赢。
   如果 buff[i-1] 和 buff[i-2] 都是输，那我就怎么拿对方都输了。
   综上：状态转移方程为：
   buff[i] = !(buff[i-1] && buff[i-2])

public class Solution {
    /**
     * @param n: An integer
     * @return: A boolean which equals to true if the first player will win
     */
    public boolean firstWillWin(int n) {
        if (n == 0) {
            return false;
        }
        
        if (n == 1 || n == 2) {
            return true;
        }
        
        boolean pre = true;
        boolean now = true;
        for (int i = 3; i <= n; i++)
        {
            boolean tmp = now;
            now = !(pre && now);
            pre = tmp;
        }
        return now;
    }
}

参考