// 演算法 / 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
    }
};