LeetCode 解題筆記：1140. Stone Game II

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


LeetCode 題目連結：1140. Stone Game II

解題想法

中等難度題，877. Stone Game 的加強版。題目給一個陣列 $piles$ 代表各個石堆的數量，兩位玩家 Alice 及 Bob 由 Alice 先行動，每回合可以從開頭拿走 $1 \leq X \leq 2M$ 堆的石頭，且下一回的 $M$ 更新為 $max(X, M)$，第一回合時 $X = 1$。題目要回傳 Alice 可以拿到的石頭數量最大值。

這題要用記憶化的動態規畫解題，在 Python 可以用裝飾器 (decorator) @cache 或是另外建一個字典儲存已經算過的值；但是 C++ 沒有裝飾器，可以用 map 儲存已經算過的值，但是 map 的速度較慢，再加上這題的 $piles$ 長度最多只有 $100$，用一個二維陣列儲存已經算過的值速度會快很多。解題步驟主要有 3 個：

1. 計算後綴和 $ssum$，$ssum[i] = piles[i] + \dots + piles[n-1]$
2. 定義函式 dfs，代入 (i, M)，計算目前的玩家由 $piles[i]$ 開始，最多可以拿 $2M$ 堆的最大數量。
3. 呼叫 dfs，代入 (0, 1)，回傳答案。

Python 程式碼

用 @cache 記憶化。Runtime: 67 ms, beats 94.78%. Memory: 26.07 MB, beats 52.86%.

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)  # 數量
        
        # 1. 建立後綴和，ssum[i] 代表 piles[i] ~ piles[n-1] 的數量加總
        ssum = [0] * n
        ssum[-1] = piles[-1]
        for i in range(n-2, -1, -1):
            ssum[i] = ssum[i+1] + piles[i]
        
        # 2. 記憶化 dfs
        @cache
        def dfs(i, M):  # 從 piles[i] 開始，最多能拿 2*M 堆
            # 遞迴出口，拿走剩下的堆
            if i + 2*M >= n:
                return ssum[i]
            # 試著拿 X 堆
            imax = 0
            for X in range(1, 2*M + 1):
                # 目前能拿的數量上限 = 現在剩下的數量 - 下一回對手能拿的數量上限
                val = ssum[i] - dfs(i+X, max(M, X))
                imax = max(imax, val)
            return imax
        
        # 3. 呼叫 dfs，由 (0, 1) 開始
        return dfs(0, 1)

用字典記憶化。Runtime: 87 ms, beats 75.73%. Memory: 23.01 MB, beats 67.30%.

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)  # 數量
        
        # 1. 建立後綴和，ssum[i] 代表 piles[i] ~ piles[n-1] 的數量加總
        ssum = [0] * n
        ssum[-1] = piles[-1]
        for i in range(n-2, -1, -1):
            ssum[i] = ssum[i+1] + piles[i]
        
        # 2. 記憶化 dfs
        memo = dict()
        def dfs(i, M):  # 從 piles[i] 開始，最多能拿 2*M 堆
            # 如果 memo 之中有已經算過的值，直接回傳
            if (i, M) in memo:
                return memo[i, M]
            # 遞迴出口，拿走剩下的堆
            if i + 2*M >= n:
                return ssum[i]
            # 試著拿 X 堆
            imax = 0
            for X in range(1, 2*M + 1):
                # 目前能拿的數量上限 = 現在剩下的數量 - 下一回對手能拿的數量上限
                val = ssum[i] - dfs(i+X, max(M, X))
                imax = max(imax, val)
            memo[i, M] = imax  # 填入 (i, M) 對應的計算結果
            return imax
        
        # 3. 呼叫 dfs，由 (0, 1) 開始
        return dfs(0, 1)

用二維串列記憶化。Runtime: 65 ms, beats 95.79%. Memory: 22.58 MB, beats 72.93%.

class Solution:
    def stoneGameII(self, piles: List[int]) -> int:
        n = len(piles)  # 數量
        
        # 1. 建立後綴和，ssum[i] 代表 piles[i] ~ piles[n-1] 的數量加總
        ssum = [0] * n
        ssum[-1] = piles[-1]
        for i in range(n-2, -1, -1):
            ssum[i] = ssum[i+1] + piles[i]
        
        # 2. 記憶化 dfs
        memo = [[-1]*(n+1) for _ in range(n)]
        def dfs(i, M):  # 從 piles[i] 開始，最多能拿 2*M 堆
            # 如果 memo[i][M] != -1，直接回傳
            if memo[i][M] != -1:
                return memo[i][M]
            # 遞迴出口，拿走剩下的堆
            if i + 2*M >= n:
                return ssum[i]
            # 試著拿 X 堆
            imax = 0
            for X in range(1, 2*M + 1):
                # 目前能拿的數量上限 = 現在剩下的數量 - 下一回對手能拿的數量上限
                val = ssum[i] - dfs(i+X, max(M, X))
                imax = max(imax, val)
            memo[i][M] = imax  # 填入 (i, M) 對應的計算結果
            return imax
        
        # 3. 呼叫 dfs，由 (0, 1) 開始
        return dfs(0, 1)

C++ 程式碼

用 map 記憶化。Runtime: 27 ms, beats 22.66%. Memory: 15.57 MB, beats 26.67%.

class Solution {
public:
    int n;  // 數量
    vector<int> ssum;  // 後綴和，ssum[i] = piles[i] + ... + piles[n-1]
    map<pair<int, int>, int> memo;  // 記憶化用的字典
    
    /* 主要的解題過程，目前從 piles[i] 開始，最多可拿 2*M 堆能拿的最大數量 */
    int dfs(int i, int M) {
        // 如果 {i, M} 在 memo 之中，直接回傳 memo[i, M]
        pair<int, int> key = make_pair(i, M);
        if (memo.count(key) == 1) {
            return memo[key];
        }
        // 遞迴出口，一次拿走剩下的堆
        if (i + 2*M >= n) {
            return ssum[i];
        }
        // 試著拿 X = 1 ~ 2*M 堆，找最大數量 imax
        int imax = 0;
        for(int X = 1; X <= 2*M; X++) {
            int val = ssum[i] - dfs(i+X, max(X, M));
            imax = max(imax, val);
        }
        memo[key] = imax;  // 更新 memo
        return imax;  // 回傳 imax
    }
    
    int stoneGameII(vector<int>& piles) {
        n = (int)piles.size();  // 更新數量
        ssum.assign(n, 0);  // 重設 ssum 為 n 個 0
        ssum[n-1] = piles[n-1];  // 由後往前填入 ssum
        for(int i = n-2; i >= 0; i--) {
            ssum[i] = ssum[i+1] + piles[i];
        }
        memo.clear();  // 呼叫 dfs 之前先清空 memo
        return dfs(0, 1);  // 從 (0, 1) 開始呼叫 dfs
    }
};

用二維陣列記憶化。Runtime: 7 ms, beats 77.21%. Memory: 13.66 MB, beats 55.90%.

class Solution {
public:
    int n;  // 數量
    vector<int> ssum;  // 後綴和，ssum[i] = piles[i] + ... + piles[n-1]
    vector<vector<int>> memo;  // 記憶化用的陣列
    
    /* 主要的解題過程，目前從 piles[i] 開始，最多可拿 2*M 堆能拿的最大數量 */
    int dfs(int i, int M) {
        // 如果 memo[i][M] != -1，直接回傳 memo[i][M]
        if (memo[i][M] != -1) {
            return memo[i][M];
        }
        // 遞迴出口，一次拿走剩下的堆
        if (i + 2*M >= n) {
            return ssum[i];
        }
        // 試著拿 X = 1 ~ 2*M 堆，找最大數量 imax
        int imax = 0;
        for(int X = 1; X <= 2*M; X++) {
            int val = ssum[i] - dfs(i+X, max(X, M));
            imax = max(imax, val);
        }
        memo[i][M] = imax;  // 更新 memo
        return imax;  // 回傳 imax
    }
    
    int stoneGameII(vector<int>& piles) {
        n = (int)piles.size();  // 更新數量
        ssum.assign(n, 0);  // 重設 ssum 為 n 個 0
        ssum[n-1] = piles[n-1];  // 由後往前填入 ssum
        for(int i = n-2; i >= 0; i--) {
            ssum[i] = ssum[i+1] + piles[i];
        }
        // 呼叫 dfs 之前先清空 memo，長度 n * (n+1) 一定夠用
        memo.assign(n, vector<int> (n+1, -1));
        return dfs(0, 1);  // 從 (0, 1) 開始呼叫 dfs
    }
};