LeetCode 解題筆記：1510. Stone Game IV

作者：王一哲
日期：2026年8月10日


LeetCode 題目連結：1510. Stone Game IV

解題想法

困難題。題目給一個正整數 $n, ~ 1 \leq n \leq 10^5$，代表這堆石頭的數量，兩位玩家 Alice、Bob 輪流取走任意平方數的石頭，如果輪到自己時已經沒有石頭則輸掉比賽，固定由 Alice 先行動，回傳 Alice 的勝負狀態。這題用動態規畫解題，定義長度為 $n+1$ 的一維陣列 $dp$，$dp[i]$ 代表石頭數量為 $i$ 時 Alice 的勝負狀態，$dp$ 預設值皆為 False。用一個 for 迴圈更新 $i = 1$ 到 $i = n$，裡面再用一個 while 迴圈，更新 $j = 1$ 到 $j^2 \leq i$，如果任何一個 $dp[i - j*j] = false$，代表 $dp[i] = true$，就可以中止內層的 while 迴圈。最後回傳 $dp[n]$。

Python 程式碼

Runtime: 596 ms, beats 56.67%. Memory: 19.92 MB, beats 85.15%.

class Solution:
    def winnerSquareGame(self, n: int) -> bool:
        # dp[i] 代表數量為 i 時 Alice 的勝負狀態，0 顆必敗，dp[0] = False
        dp = [False] * (n+1)
        # 跑 i = 1 ~ n，檢查所有小於等於 i 的平方數 j，如果 dp[i - j*j] = False，則 dp[i] = True
        for i in range(1, n+1):
            j = 1
            while j*j <= i:
                if not dp[i - j*j]:
                    dp[i] = True
                    break
                j += 1
        return dp[n]

C++ 程式碼

Runtime: 31 ms, beats 81.44%. Memory: 8.85 MB, beats 90.65%.

class Solution {
public:
    bool winnerSquareGame(int n) {
        // dp[i] 代表數量為 i 時 Alice 的勝負狀態，0 顆必敗，dp[0] = False
        vector<bool> dp (n+1, false);
        // 跑 i = 1 ~ n，檢查所有小於等於 i 的平方數 j，如果 dp[i - j*j] = False，則 dp[i] = True
        for(int i = 1; i <= n; i++) {
            int j = 1;
            while(j*j <= i) {
                if (!dp[i - j*j]) {
                    dp[i] = true;
                    break;
                }
                j++;
            }
        }
        return dp[n];
    }
};

改用 array 速度更快。Runtime: 15 ms, beats 95.36%. Memory: 7.90 MB, beats 98.31%.

class Solution {
public:
    bool winnerSquareGame(int n) {
        // dp[i] 代表數量為 i 時 Alice 的勝負狀態，0 顆必敗，dp[0] = False
        bool dp[100001] = {false};
        // 跑 i = 1 ~ n，檢查所有小於等於 i 的平方數 j，如果 dp[i - j*j] = False，則 dp[i] = True
        for(int i = 1; i <= n; i++) {
            int j = 1;
            while(j*j <= i) {
                if (!dp[i - j*j]) {
                    dp[i] = true;
                    break;
                }
                j++;
            }
        }
        return dp[n];
    }
};

C 語言程式碼

Runtime: 19 ms, beats 72.73%. Memory: 8.66 MB, beats 54.55%.

bool winnerSquareGame(int n) {
    bool dp[100001] = {false};
    for(int i = 1; i <= n; i++) {
        int j = 1;
        while(j*j <= i) {
            if (!dp[i - j*j]) {
                dp[i] = true;
                break;
            }
            j++;
        }
    }
    return dp[n];
}