阅读 50

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

文章分类
代码人生
版权声明:本站是系统测试站点,无实际运营。本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容, 请发送邮件至 XXXXXXo@163.com 举报,一经查实,本站将立刻删除。
相关推荐