0292. Nim 游戏【简单】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 数学解法（最优解）
• 3. 🎯 s.2 - 动态规划解法（用于理解思路）
• 4. 🔗 引用

1. 📝 题目描述

• leetcode

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

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

假设你们每一步都是最优解。

请编写一个函数，来判断你是否可以在给定石头数量为 n 的情况下赢得游戏。

• 如果可以赢，返回 true；
• 否则，返回 false。

---

示例 1：

输入：n = 4
输出：false
解释：以下是可能的结果:
1. 移除1颗石头。你的朋友移走了3块石头，包括最后一块。你的朋友赢了。
2. 移除2个石子。你的朋友移走2块石头，包括最后一块。你的朋友赢了。
3.你移走3颗石子。你的朋友移走了最后一块石头。你的朋友赢了。
在所有结果中，你的朋友是赢家。

示例 2：

输入：n = 1
输出：true

示例 3：

输入：n = 2
输出：true

---

提示：

• 1 <= n <= 2^31 - 1

2. 🎯 s.1 - 数学解法（最优解）

js

/**
 * @param {number} n
 * @return {boolean}
 */
var canWinNim = function (n) {
  // 当 n 能被 4 整除时，先手必败；否则先手必胜
  return n % 4 !== 0
}

• 时间复杂度：$O(1)$
• 空间复杂度：$O(1)$
• 算法思路：
  • 让我们从小到大分析一下：
    • n = 1, 2, 3：先手可以直接拿走所有石子，先手必胜
    • n = 4：先手无论拿 1、2 还是 3 颗，都会给对手留下 3、2 或 1 颗石子，对手必胜，先手必败
    • n = 5, 6, 7：先手可以拿适当数量的石子，给对手留下 4 颗石子，根据上面的分析，对手必败，先手必胜
    • n = 8：先手无论拿 1、2 还是 3 颗，都会给对手留下 7、6 或 5 颗石子，对手必胜，先手必败
  • 通过归纳可以发现规律：当 n 能被 4 整除时，先手必败；否则先手必胜。

3. 🎯 s.2 - 动态规划解法（用于理解思路）

js

/**
 * @param {number} n
 * @return {boolean}
 */
var canWinNim = function (n) {
  // 对于大数值，直接使用数学解法避免内存问题
  if (n > 1000000) {
    return n % 4 !== 0
  }

  // dp[i] 表示有 i 颗石子时，先手是否能赢
  const dp = new Array(n + 1)

  // 基础情况
  for (let i = 1; i <= Math.min(3, n); i++) {
    dp[i] = true // 1~3 颗石子，先手可以直接拿完获胜
  }

  // 状态转移
  for (let i = 4; i <= n; i++) {
    // 有 i 颗石子时，如果我方回合拿走石子（1或2或3）后，能让对手必败，则我方必胜
    dp[i] =
      !dp[i - 1] || // 我方拿 1 颗后，对手面对 i-1 必败
      !dp[i - 2] || // 我方拿 2 颗后，对手面对 i-2 必败
      !dp[i - 3] // 我方拿 3 颗后，对手面对 i-3 必败
  }

  return dp[n]
}

• 时间复杂度：$O(n)$
• 空间复杂度：$O(n)$
• 算法思路：
  1. 状态定义：dp[i] 表示有 i 颗石子时先手是否能赢
  2. 初始状态：dp[1] = dp[2] = dp[3] = true
  3. 状态转移：dp[i] = !dp[i-1] || !dp[i-2] || !dp[i-3]
     • 如果拿 1、2、3 颗石子后，对手处于必败态，则先手必胜

4. 🔗 引用

• Nim 游戏
  • 百度百科