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;
}