日期：2026年8月24日
LeetCode 題目連結：1872. Stone Game VIII
解題想法
困難題。題目給一個陣列 $stones$ 代表一列石頭由左到右的分數，Alice 與 Bob 兩人輪流從左邊拿走 $x$ 個石頭，且 $x > 1$，可以獲得拿走的石頭的總分，然後將一個等於總分的石頭放在最左邊，只剩下一個石頭時遊戲結束，固定由 Alice 先行動。假設 Alice 要使分差最大，Bob 要使分差最小，回傳遊戲結束時的分差。
由於每次行動時會拿走前 $x$ 顆石頭，再將一顆等於總分的石頭放在最左邊，因此下一個人行動時拿到的石頭會包含上一次取走的 $x$ 顆石頭的總分。計算分差時會用到前 $x$ 顆石頭的總分，可以先建立前綴和陣列 $psum$。這題要用動態規畫解題，理論上比較適合由最後的狀態往回推。假設 $dp[i]$ 代表處理 $stones[i]$ 時的最大分差，邊界條件為最後一次行動時會拿走所有的石頭，也就是 $i = n-1$ 時 $dp[i] = psum[n-1]$。更新狀態時有兩種可能性：
- 拿走 $stones[i]$，最大分差為 $psum[i] - dp[i+1]$
- 不拿 $stones[i]$，最大分差為 $dp[i+1]$
另一個寫法是由 $i = 0$ 開始處理，並用記憶化及遞迴往下找 $i + 1$ 的狀態，直到 $i = n-1$ 時結束遞迴。如果在 Python 用這個寫法，必須引入 sys 函式庫，並用 sys.setrecursionlimit(200000) 調整遞迴深度，否則會遇到遞迴深度過深的問題。
Python 程式碼
方法1。Runtime: 674 ms, beats 65.09%. Memory: 32.25 MB, beats 98.22%.
class Solution:
def stoneGameVIII(self, stones: List[int]) -> int:
# 建立前綴和陣列
n = len(stones)
psum = stones[:]
for i in range(1, n):
psum[i] += psum[i-1]
"""
動態規畫，dp[i] 代表選擇索引值 i 的最大分差，由最後的狀態往前推
狀況1，選擇拿 psum[i]，下一個狀態的 dp[i+1]，目前最大分差為 psum[i] - dp[i+1]
狀況2，不拿 psum[i]，目前最大分差為 dp[i+1]
"""
dp = psum[-1] # 邊界條件，最後一次要全部拿走
for i in range(n-2, 0, -1): # 只跑 i = n-2 ~ 1，因為一次至少拿 2 個石頭
dp = max(psum[i] - dp, dp)
return dp
方法2。Runtime: 770 ms, beats 14.20%. Memory: 83.57 MB, beats 11.24%.
import sys
sys.setrecursionlimit(200000) # 調整遞迴深度
class Solution:
def stoneGameVIII(self, stones: List[int]) -> int:
# 建立前綴和陣列
n = len(stones)
psum = stones[:]
for i in range(1, n):
psum[i] += psum[i-1]
# 記憶化及遞迴
memo = [None] * n
def dfs(i): # 目前選擇索引值 i
# 遞迴出口，最後一次只能全拿
if i == n-1:
return psum[-1]
# 如果 memo 之中有已經算過的值，直接回傳
if memo[i] is not None:
return memo[i]
# 狀態轉移
skip = dfs(i+1) # 不拿 psum[i]
take = psum[i] - skip # 拿 psum[i]
memo[i] = max(take, skip) # 選擇較大者
return memo[i]
# 呼叫 dfs，代入 i = 1，因為至少要拿 2 顆石頭
return dfs(1)
