题目主要信息

这是一个经典的博弈。

你和你的朋友，两个人玩一个游戏。

1.桌子上有 n 个石头

2.你和你的朋友轮流取石头，你先手。

3.每一回合可以取 1~3 个石头。

4.轮到你的朋友时桌上没有石头则你获胜，则你的朋友获胜。

你和你的朋友都尽力让自己获胜，如果你有方法必胜，则返回 true ，如果你的朋友有方法必胜，则返回 false

方法一：数学推导

具体方法

如果石头堆中只有一块、两块、或是三块石头，那么在你的回合，你就可以把全部石子拿走，从而在游戏中取胜；如果堆中恰好有四块石头，你就会失败。

因为在这种情况下不管你取走多少石头，总会为你的对手留下几块，他可以将剩余的石头全部取完，从而他可以在游戏中打败你。因此，要想获胜，在你的回合中，必须避免石头堆中的石子数为 44 的情况。

• 当n = 4、8、12....四的倍数，你都会输。假设当前堆里只剩下五块、六块、或是七块石头，你可以控制自己拿取的石头数，总是恰好给你的对手留下四块石头，使他输掉这场比赛。但是如果石头堆里有八块石头，你就不可避免地会输掉，因为不管你从一堆石头中挑出一块、两块还是三块，你的对手都可以选择三块、两块或一块，以确保在再一次轮到你的时候，你会面对四块石头。基本可以看出如果堆里的石头数目为 4 的倍数时，你一定会输掉游戏。
• 如果总的石头数目为 4 的倍数时，因为无论你取多少石头，对方总有对应的取法，让剩余的石头的数目继续为 4 的倍数。对于你或者你的对手取石头时，显然最优的选择是当前己方取完石头后，让剩余的石头的数目为 4 的倍数。假设当前的石头数目为 x，如果 x 为 4 的倍数时，则此时你必然会输掉游戏；如果 xx 不为 4 的倍数时，则此时你只需要取走xmod4 个石头时，则剩余的石头数目必然为 4 的倍数，从而对手会输掉游戏。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return bool布尔型
     */
    public boolean NimGame (int n) {
        // write code here
        return n%4 !=0;
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}1\mathrm{）}O（1）$，直接返回结果
• 空间复杂度：$O\mathrm{（}1\mathrm{）}O（1）$，直接返回结果

方法二：动态规划

具体方法

• 状态定义：dp[i]表示i个石头时是否能获胜。
• 状态初始化：i为1、2、3时，先手必定获胜，赋值为true。
• 状态转移：只要检查i-1、i-2、i-3个石头时是否能赢，即可判断当前i个石头是否能赢。即$dp[i]=!dp[i\mathrm{-}1]\mid \mid !dp[i\mathrm{-}2]\mid \mid !dp[i\mathrm{-}3]dp[i]=!dp[i-1]\mid \mid !dp[i-2]\mid \mid !dp[i-3]$
• 当测试数据较大时，dp数组会特别大，所以运行报堆空间溢出。

代码实现

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @return bool布尔型
     */
    public boolean NimGame (int n) {
        // write code here
                //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];
    }
}

复杂度分析

• 时间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，需要$\mathrm{（}n-3\mathrm{）}\ast 3（n-3）*3$次遍历
• 空间复杂度：$O\mathrm{（}n\mathrm{）}O（n）$，数组的大小