你和你的朋友，两个人一起玩Nim游戏：
规则是：
- 桌子上有一堆石头。
- 你们轮流进行自己的回合， 你作为先手 。
- 每一回合，轮到的人拿掉 1 – 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。
示例 1：
输入：n = 4
输出：false
解释：以下是可能的结果:
1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。
示例 2：
输入：n = 1
输出：true
示例 3：
输入：n = 2
输出：true
提示：
1 <= n <= 231 - 1
思路:
最自然的想法当然是使用动态规划， 从拿1颗， 2颗和3颗三种情况分别去看能不能归约到对方一次拿完的情况，以此来判定是否是必输局面：
class Solution {
public:
bool canWinNim(int n) {
if (n <= 3) return true;
vector<bool> dp(4, false);
dp[0] = false;
dp[1] = true;
dp[2] = true;
dp[3] = true;
for (int i = 4; i <= n; i++) {
dp[i % 4] = (!dp[(i-1) % 4] || !dp[(i-2) % 4] || !dp[(i-3) % 4]);
}
return dp[n % 4];
}
};Code language: PHP (php)然而这不会AC, 因为1 <= n <= 231 - 1, 动态规划在这样的数量上一定会超时。
所以应该分析游戏本身：
- 当
n = 1,n = 2,n = 3， 先手都能一次拿走所有石头， 是先手必赢局 - 当
n = 4， 先手拿取石头后剩下的石头数都能被后手一次取完， 是先手必输局 - 当
n = 5， 先手拿取石头后，可能剩下的石头数分别为4, 3, 2，3颗和2颗可以后手一次拿取， 后手胜；但剩余4颗的时后手便面临n = 4的情况，后手必输。因此这是先手必赢的局面， 应该返回true。 - 当
n = 6， 先手拿取石头后，可能剩下的石头数分别为5, 4, 3- 剩余
3颗时后手可以一次拿取， 后手胜 - 剩余
4颗时后手面临n = 4的情况， 后手败 - 剩余
5颗时后手面临n = 5的情况， 后手胜 - 因此这仍是先手必赢的局面， 应该返回
true。
- 剩余
- 很容易发现, Nim游戏的先手必胜与否可表示为一个函数 \(f(n)\) : $$ f(n) = \begin{cases} f(n-1) \oplus f(n-2) \oplus f(n-3) &n \geq 4 \\ 1&n=3\\ 1&n=2\\ 1&n=1 \end{cases} $$, 其中 \(\oplus\) 表示异或，
n为起始石子数。 - 容易注意到, 每4局就会出现一次先手必败局面, 所以只需要判断初始石子数是否能被4整除，即可判断当前局面是否为先手必胜局。
AC代码:
这道题评为Easy级是有原因的：
class Solution {
public:
bool canWinNim(int n) {
return n%4 ;
}
};Code language: C++ (cpp)