292. Nim 游戏

你和你的朋友，两个人一起玩 Nim 游戏：

• 桌子上有一堆石头。
• 你们轮流进行自己的回合，你作为先手。
• 每一回合，轮到的人拿掉 1 - 3 块石头。
• 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

示例 1：

输入：n = 4
输出：false
解释：如果堆中有 4 块石头，那么你永远不会赢得比赛；
因为无论你拿走 1 块、2 块 还是 3 块石头，最后一块石头总是会被你的朋友拿走。

示例 2：

输入：n = 1
输出：true

示例 3：

输入：n = 2
输出：true

提示：

• 1 <= n <= 231 - 1

思路

我有一个朋友是ACM的银牌得主，知道巴什博弈不过分吧。

1）方法一：巴什博弈

在先取完者胜的巴什博弈中，若n可被m+1整除，则后手方必胜，否则先手方必胜。

详细的策略分析参考百度百科：巴什博弈。

在题目中一次最多可以拿3个石头，所以上图的m = 3；

代码

class Solution {

    /**
     * 方法：巴什博弈
     * 时间复杂度、空间复杂度：O(1)
     *
     * @param n 石头总数
     */
    public boolean canWinNim(int n) {
        return bashGame(n, 3);
    }

    /**
     * 巴什博弈
     *
     * @param totalCount 石头总数
     * @param topStep    一次最多可以拿的石头个数
     */
    private boolean bashGame(int totalCount, int topStep) {
        // 先手获胜的结果
        return totalCount % (topStep + 1) != 0;
    }
}

2）方法二：暴力递归（会超时）

找规律，多写几个数就能找到规律：

依照题意，令函数f(n)表示n个石子能否获胜。则f(n) = !f(n-1) or !f(n-2) or !f(n-3) ；

• 因为f(n-1)表示朋友能否赢，而我的状态与之相反；
• 又在取1、2、3个石头操作中，只要有一个策略能赢即可。 嘿嘿，这不是典型的递归公式嘛。

代码

public boolean canWinNim(int n) {
    if(n<=3) {
        return true;
    } else {
        // 不管我先拿1个、2个、3个石头，后手都能赢；否则先手的我赢
        return !(canWinNim1(n-1) && canWinNim1(n-2) && canWinNim1(n-3));
    }
}

递归超时的原因？

自顶向下的递归，反复用到了大量重复数据，导致了不必要的开销。

解决重复数据的方法：

• 1、用记忆化数组存储用到过的数据，减少不必要的开销。即下面的 方法三：动态规划
• 2、迭代，使用几个变量代替动态规划的数组。即下面的方法四：迭代

3）方法三：动态规划（有可能超出内存限制）

用记忆化数组dp存储用到过的数据；但当n很大时，可能会超出内存限制；

public boolean canWinNim(int n) {
    if(n <= 3) return true;
    boolean[] dp = new boolean[n+1];
    dp[1] = true;
    dp[2] = true;
    dp[3] = true;

    for (int i = 4; i <= n; i++) {
        // 不管我先拿1个、2个、3个石头，后手都能赢；否则先手的我赢
        dp[i] = !(dp[i-1]&&dp[i-2]&&dp[i-3]);
    }
    return dp[n];
}

开辟数组dp有点浪费内存空间，因为自底向上的方法中并不需要存储之前用到过的很多数据，它是逐步向前的，而与当前这一步有关的值只有前三个数。

3）方法四：迭代（有可能超时）

使用四个变量（a、b、c、temp）代替动态规划dp数组，释放不必要的内存空间占用；当n很大时，仍然可能会超时；

public boolean canWinNim(int n) {
    if(n <= 3) return true;
    boolean a=true;
    boolean b=true;
    boolean c=true;
    boolean temp;
    for (int i = 4; i <= n; i++) {
        // 不管我先拿1个、2个、3个石头，后手都能赢；否则先手的我赢
        temp = !(a && b && c);
        a = b;
        b = c;
        c = temp;
    }
    return c;
}