LeetCode Nim Game：尼姆遊戲必勝策略

題目描述

堆有 n 顆石子，雙方輪流取 1~3 顆，取走最後一顆者勝。你先手。雙方均最優策略。判斷你能否獲勝。

博弈論分析

• 1,2,3 顆：先手全拿 → 勝。
• 4 顆：先手拿 1/2/3，剩 3/2/1，後手全拿 → 先手敗。
• 5 顆：先手拿 1，剩 4 → 後手面對 4 必敗 → 先手勝。
• 6 顆：先手拿 2，剩 4 → 勝。
• 7 顆：先手拿 3，剩 4 → 勝。
• 8 顆：先手無論拿幾，剩 5/6/7，後手可拿至 4 → 先手敗。

規律：n % 4 == 0 先手必敗，否則先手必勝。策略：先手讓剩餘為 4 的倍數，後手則每次取 4 - 對手取數。

代碼

class Solution {
public:
    bool canWinNim(int n) {
        return n % 4 != 0;
    }
};