力扣每日一題2021-09-18Nim遊戲

Nim遊戲

• 292.Nim遊戲
• • 題目描述
  • 思路：博弈論

292.Nim遊戲

題目描述

Nim遊戲

思路：博弈論

由于每個人每次都隻能取1~3個石頭，，那麼第二個人總能通過取第一個人取法跟4的補數的2石頭，而達到穩定取得4或其他4的倍數的目的。即隻要總石子個數為4的倍數，則後手一方永遠能取到。

至于其他不是4的倍數的石子，先手的人可以通過取餘數達到讓自己成為上述的穩定取得4的倍數的石子的“後手”，獲得穩定的勝利。

class Solution:
    def canWinNim(self, n: int) -> bool:
        return n % 4 != 0