题解 | #Nim游戏#

题意整理

• A和B玩一个游戏。
• 桌子上有n个石头，A、B轮流从桌子上取石头，每一回合可以取1-3个，谁最先取完石头则获胜，否则另一方获胜。
• 给定石头数n，判断最终谁会获得胜利。

方法一（动态规划）

1.解题思路

• 状态定义：$dp[i]dp[i]$表示i个石头时是否能获胜。
• 状态初始化：i为1、2、3时，先手必定获胜，赋值为true。
• 状态转移：只要检查i-1、i-2、i-3个石头时是否能赢，即可判断当前i个石头是否能赢。即$dp[i]=!dp[i-1]\mathrm{\mid }\mathrm{\mid }!dp[i-2]\mathrm{\mid }\mathrm{\mid }!dp[i-3]dp[i]\; =!dp[i-1]||!dp[i-2]||!dp[i-3]$。

当测试数据较大时，dp数组会特别大，所以运行报堆空间溢出。

2.代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return bool布尔型
     */
    public boolean NimGame (int n) {
        //n为1、2、3时必胜
        if(n<=3) return true;
        //定义dp数组，dp[i]表示i个石头时是否能获胜
        boolean[] dp=new boolean[n+1];
        //初始化
        dp[1]=dp[2]=dp[3]=true;
        
        for(int i=4;i<=n;i++){
            //只要取1-3个石头后，对应的状态是必输状态，则当前必能赢
            for(int j=1;j<=3;j++){
                if(!dp[i-j]){
                    dp[i]=true;
                }
            }
        }
        return dp[n];
    }
}

3.复杂度分析

• 时间复杂度：循环最多智行$(n-3)\ast 3(n-3)*3$次，所以时间复杂度是$O(n)O(n)$。
• 空间复杂度：需要额外大小为$n+1n+1$的dp数组，所以空间复杂度为$O(n)O(n)$。

方法二（数学）

1.解题思路

当n为1、2、3时，只要先手取光石头，即可获胜，所以先手必胜。当n为4时，不管先手取1个、2个还是3个石头，剩下的石头都可以被后手取完，所以先手必败。当n为5、6、7时，只要取对应的石头，剩下的石头都可以变成4，从而后手必败，即先手必胜。同样，当n取8时，无论先手怎么取，留给后手的一定是5个、6个或7个石头，所以后手必胜，先手必败。依此类推先手取4，8，12，16，……时，一定会输给后手。

图解展示：

2.代码实现

import java.util.*;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return bool布尔型
     */
    public boolean NimGame (int n) {
        //分析规律可知，只要n不是4的倍数，则必胜
        return n%4!=0;
    }
}

3.复杂度分析

• 时间复杂度：只需一次运算，所以时间复杂度是$O(1)O(1)$。
• 空间复杂度：不需要额外内存空间，所以空间复杂度为$O(1)O(1)$。