leetcode292.Nim游戏——leetcode每日一题2021.9.18
292. Nim游戏
你和你的朋友,两个人一起玩 Nim 游戏:
- 桌子上有一堆石头。
- 你们轮流进行自己的回合,你作为先手。
- 每一回合,轮到的人拿掉 1 - 3 块石头。
- 拿掉最后一块石头的人就是获胜者。
假设你们每一步都是最优解。请编写一个函数,来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢,返回
true
;否则,返回false
。
题目链接:
动态规划
思路:第一眼就是动态规划,but出错了MemoryError
-
dp[i]
表示剩余i块石头时当前轮次选手的结局 -
当轮到自己时石头堆还剩1~3块石头,那此人必赢
dp[1] = dp[2] = dp[3] = True
-
当轮到自己时石头堆还剩0块石头,必输
dp[0] = False
-
我是否能赢取决于对手是否能赢
- 当我取完石块之后,如果对手无论怎么取都赢,那我必输
- 否则我必赢
class Solution:
def canWinNim(self, n: int) -> bool:
if n in [1,2,3]:
return True
dp = [False]*(n+1)
dp[1] = dp[2] = dp[3] = True
for i in range(4,n+1):
if (dp[i-1] and dp[i-2] and dp[i-3]):
dp[i] = False
else:
dp[i] = True
return dp[-1]
博弈论
思路:
可以枚举一下,剩1~3块石头可以直接全部拿走,必胜。
剩4块石头,无论你取几块石头,剩下的石块对手都可以一次性拿走,必输。
剩5块石头,我先拿一块,那就可以让对方陷入4块石头必输的境地。能赢。
剩6块石头,同上,先拿两块,能赢。
剩7块石头,同上,先拿三块,能赢。
剩8块石头,无论我拿几块,对方都会回到上面5、6、7的情况让我陷入4块石头的境地,必输。
依次类推我们可以发现,当石头堆的数量为4的倍数时,当前轮次的人必输。
class Solution:
def canWinNim(self, n: int) -> bool:
if n%4 == 0:
return False
else:
return True
原文:https://www.cnblogs.com/waitting975/p/15308033.html