leetcode292.Nim游戏——leetcode每日一题2021.9.18

292. Nim游戏

你和你的朋友，两个人一起玩 Nim 游戏：

• 桌子上有一堆石头。
• 你们轮流进行自己的回合，你作为先手。
• 每一回合，轮到的人拿掉 1 - 3 块石头。
• 拿掉最后一块石头的人就是获胜者。

假设你们每一步都是最优解。请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。如果可以赢，返回 true；否则，返回 false 。

题目链接： 292. Nim 游戏 - 力扣（LeetCode） (leetcode-cn.com)

动态规划

思路：第一眼就是动态规划，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