1510. Stone Game IV

題目 / Problem

中文： Alice 和 Bob 輪流玩遊戲，Alice 先手。一開始有 n 顆石頭。每一回合，當前玩家必須從石堆中拿走 任意一個非零的完全平方數 顆石頭（例如 1、4、9、16…）。如果輪到某位玩家時他無法行動（沒有石頭可拿），他就輸了。給定正整數 n，假設雙方都採取最佳策略，若 Alice 必勝就回傳 true，否則回傳 false。

English: Alice and Bob take turns, Alice first. There are n stones. On each turn a player must remove a non-zero perfect-square number of stones (1, 4, 9, 16, …). A player who cannot move loses. Given n, return true if Alice wins with optimal play, otherwise false.

Constraints / 限制： - 1 <= n <= 10^5

Example / 範例： - n = 2 → false。Alice 只能拿 1 顆（2 → 1），Bob 再拿走最後 1 顆（1 → 0），輪到 Alice 時沒有石頭，Alice 輸。 - n = 4 → true。4 本身是完全平方數，Alice 一次拿走 4 顆（4 → 0），Bob 無法行動，Alice 贏。

名詞解釋 / Glossary

• 完全平方數 / Perfect square：某個整數的平方，例如 1=1²、4=2²、9=3²、16=4²。本題每次只能拿走這種數量的石頭。 A number that equals an integer squared.
• 動態規劃 / Dynamic Programming (DP)：把大問題拆成小問題，先算小的、把答案存起來，之後直接查表，避免重複計算。 Break a problem into smaller subproblems, solve each once, store the answer, reuse it.
• 狀態 / State：這裡的「狀態」就是「輪到某人時，石堆裡還剩幾顆石頭」。我們用 dp[i] 表示「面對 i 顆石頭、且輪到你行動」時你是否會贏。 The situation we track: i stones left and it is your move.
• 必勝態 / 必敗態 (Winning / Losing state)：dp[i] = true 代表當前要行動的人能贏（必勝態）；dp[i] = false 代表當前要行動的人會輸（必敗態）。 Whether the player to move wins.
• 最佳策略 / Optimal play：雙方都不會犯錯，永遠選能讓自己贏的走法。 Both players always pick the best possible move.

思路

我們先想暴力法：從 n 開始，Alice 嘗試每一個可拿的完全平方數，然後 Bob 面對剩下的石頭也嘗試每一種走法……這樣一路遞迴下去。問題是同一個「剩餘石頭數」會被重複計算非常多次，時間會爆炸。這正是動態規劃的用武之地——因為「輸贏只取決於現在剩幾顆石頭，跟之前怎麼拿的無關」。

我們定義 dp[i] = 「當輪到你、石堆裡有 i 顆時，你是否必勝」。基底情況是 dp[0] = false：沒有石頭可拿，輪到你就直接輸。關鍵的遞推想法是：從 i 顆出發，你可以拿走某個完全平方數 k*k（只要 k*k <= i），這樣就把 i - k*k 顆石頭「丟給對手」。如果存在某個走法，使得對手面對的狀態 dp[i - k*k] 是 必敗態（false），那你就能靠這一步逼對手輸，所以 dp[i] = true。只要有一個這樣的走法就夠了。反之，如果你試過所有平方數，對手每一次都落在必勝態，那你怎麼走都會輸，dp[i] = false。我們從 1 算到 n，每個狀態只算一次並存起來，最後回傳 dp[n]。這裡的核心不變量是：dp[i] 一旦算好就固定不變，且只依賴比它更小的狀態，所以由小到大填表一定正確。

Start with brute force: from n, Alice tries every removable square, then Bob does the same on what remains, recursing forever. The trouble is the same "number of stones remaining" gets recomputed a huge number of times. DP fixes this because the winner depends only on how many stones remain right now, not on the history of moves. Define dp[i] = "with i stones and it is your move, do you win?" The base case is dp[0] = false: no stones to take means you lose immediately. The recurrence: from i, you may remove a square k*k (as long as k*k <= i), handing your opponent the state i - k*k. If any such move leaves the opponent in a losing state (dp[i - k*k] == false), then you can force their loss, so dp[i] = true. Just one good move is enough. If every square leaves the opponent winning, then you lose no matter what, so dp[i] = false. We fill the table from 1 up to n, computing each state once, and return dp[n]. The invariant that makes bottom-up filling correct: dp[i] depends only on strictly smaller states, which are all already computed.

逐步走查 / Walkthrough

以 n = 4 為例，逐步建表 / Trace for n = 4, filling dp[0..4]：

最終 dp[4] = true，所以 Alice 必勝，回傳 true。/ Final dp[4] = true, so Alice wins.

Solution — C

// 演算法 / Algorithm:
// dp[i] = 面對 i 顆石頭且輪到你時是否必勝 / whether the player to move with i stones wins.
// dp[0]=false（不能動就輸）。對每個 i，試每個平方數 k*k；若某個 dp[i-k*k] 為 false，
// 代表能把必敗態丟給對手，故 dp[i]=true。/ If any move hands the opponent a losing state, you win.

#include <stdbool.h>   // 讓 C 能使用 bool / true / false / enables bool, true, false
#include <stdlib.h>    // 提供 calloc / free / for calloc and free

bool winnerSquareGame(int n) {
    // 配置 n+1 個 bool，索引 0..n；calloc 會把每格初始化為 0（即 false）
    // Allocate n+1 bools, indices 0..n; calloc zero-initializes every cell to false.
    bool *dp = (bool *)calloc(n + 1, sizeof(bool));

    // dp[0] 已是 false，代表 0 顆石頭時輪到你就輸 / dp[0] stays false: 0 stones = you lose.
    for (int i = 1; i <= n; i++) {          // 由小到大填表 / fill states from small to large
        // 試每個非零平方數 k*k，只要不超過 i / try each square k*k that fits in i
        for (int k = 1; k * k <= i; k++) {  // k*k 是這一步要拿走的石頭數 / stones removed this move
            // 拿走 k*k 後，對手面對 dp[i - k*k]；若它是必敗態(false)，我方就贏
            // After removing k*k, opponent faces dp[i - k*k]; if that is losing, we win.
            if (!dp[i - k * k]) {           // '!' 是邏輯反：!false == true / '!' negates the bool
                dp[i] = true;               // 找到必勝走法，記為必勝態 / found a winning move
                break;                       // 一個就夠，跳出內層迴圈 / one is enough, stop looking
            }
        }
        // 若迴圈走完都沒 break，dp[i] 仍是 calloc 給的 false（必敗態）
        // If no break happened, dp[i] remains false: a losing state.
    }

    bool ans = dp[n];   // 答案就是 n 顆石頭時先手(Alice)是否必勝 / answer for the starting state
    free(dp);           // 釋放先前 calloc 的記憶體，避免記憶體洩漏 / release the allocated memory
    return ans;         // 回傳結果 / return the result
}

Solution — C++

// 演算法 / Algorithm:
// dp[i] = 面對 i 顆石頭且輪到你時是否必勝 / whether the mover with i stones wins.
// 從 i 出發試每個平方數 k*k；若某個 dp[i-k*k]==false，就能把必敗態丟給對手，故 dp[i]=true。
// If any move leaves the opponent in a losing state, the current player wins.

#include <vector>   // 提供 std::vector（可自動管理記憶體的動態陣列）/ dynamic array container

class Solution {
public:
    bool winnerSquareGame(int n) {
        // vector<bool> 建立長度 n+1 的表，全部初始化為 false（必敗態的預設值）
        // Build a length-(n+1) table, all initialized to false (default losing state).
        std::vector<bool> dp(n + 1, false);

        for (int i = 1; i <= n; ++i) {            // 由小到大填每個狀態 / fill each state bottom-up
            for (int k = 1; k * k <= i; ++k) {    // 枚舉可拿的平方數 k*k / enumerate squares that fit
                // 若對手面對的 dp[i - k*k] 是必敗態，這步就讓我方必勝
                // If the opponent's resulting state is losing, this move wins for us.
                if (!dp[i - k * k]) {             // '!' 取反：找到 false 就代表對手必敗 / found a losing target
                    dp[i] = true;                 // 標記為必勝態 / mark current state as winning
                    break;                         // 找到一個必勝走法即可停 / one winning move suffices
                }
            }
            // 沒進 if 的話，dp[i] 保持 false，表示所有走法都讓對手必勝
            // Otherwise dp[i] stays false: every move hands the opponent a win.
        }

        return dp[n];   // n 顆石頭時 Alice(先手)是否必勝 / does the first player win with n stones
    }
};

複雜度 / Complexity

• Time: O(n · √n) — 外層迴圈跑 n 次；對每個 i，內層只枚舉到 k*k <= i，也就是最多約 √i ≤ √n 個平方數。兩者相乘即 n√n。 The outer loop runs n times; for each i the inner loop tries only about √i squares, so total work is n · √n.
• Space: O(n) — 需要一個長度 n+1 的 dp 陣列來保存每個狀態的輸贏；除此之外只用了常數個變數。 One dp array of size n+1 stores every state's result; everything else is constant.

Pitfalls & Edge Cases

• 必敗態才是「好目標」/ You want to hand the opponent a false：新手容易寫成「若 dp[i-k*k] 為 true 就贏」，方向剛好相反。你贏是因為對手接到的是 必敗態，所以條件是 !dp[i - k*k]。 The winning condition checks that the opponent's state is losing, not winning.
• 迴圈邊界用 k*k <= i 而非 k <= i / Loop bound：一定要用 k * k <= i，否則會多枚舉、甚至讓 i - k*k 變負而越界。用 k*k 也自然避免了對 i 取平方根的浮點誤差。 Using k*k <= i avoids negative indices and floating-point sqrt issues.
• k*k 的整數溢位不是問題 / No overflow here：因為 n <= 10^5，k 最多約 316，k*k 遠在 int 範圍內；但若題目放大，需注意 k*k 可能溢位。 With n <= 10^5, k*k stays well within int.
• dp[0] 必須是 false / Base case must be false：這是整個遞推的錨點——0 顆石頭代表輪到的人不能動而輸。calloc / vector(...,false) 已幫我們設好，別手動改成 true。 The base case dp[0]=false anchors the recurrence; leave it false.
• C 版記得 free / Free the memory in C：calloc 配置的記憶體要 free，否則造成記憶體洩漏；C++ 的 vector 會自動釋放，不需手動處理。 The C version must free the array; the C++ vector cleans up itself.