日期：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 個：
- 計算後綴和 $ssum$，$ssum[i] = piles[i] + \dots + piles[n-1]$
- 定義函式 dfs，代入 (i, M)，計算目前的玩家由 $piles[i]$ 開始，最多可以拿 $2M$ 堆的最大數量。
- 呼叫 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)
