日期：2026年8月17日
LeetCode 題目連結：1563. Stone Game V
解題想法
困難題。題目給一個長度為 $n$ 的陣列 $stoneValue$ 代表每個石頭的分數，個回合 Alice 可以選擇一個分割點，將這列石頭分成左、右半邊，Bob 會將總分較高的半邊丢掉，Alice 可以獲得留下半邊石頭的總分，題目要問 Alice 最多可以拿幾分。由於這個題目需要不斷地計算區問和，需要先建立前綴和陣列 $psum$。接下來用動態規畫解題，定義大小為 $n \times n$ 的二維陣列 $dp$，$dp[i][j]$ 代表 Alice 在區間 i ~ j 能獲得的最高分，最後答案會在 $dp[0][n-1]$。填滿 $dp$ 的方法有兩種，第一種較簡單但是時間複雜度為 $O(n^3)$，用 Python 會超時，C 與 C++ 可以過關，但是時間排名很後面；第二種較複雜但是時間複雜度為 $O(n^2)$，用 Python、C、C++ 都能過關。
Python 程式碼
方法1，超時。
class Solution:
def stoneGameV(self, stoneValue: List[int]) -> int:
n = len(stoneValue) # 數量
# 1. 建立前綴和，之後可以用來查詢區間和
psum = [0] * (n+1) # pusm 的索引值比 stoneValue 多 1
for i in range(1, n+1):
psum[i] = psum[i-1] + stoneValue[i-1]
# 2. 建立動態規畫陣列，dp[i][j] 代表在區間 [i...j] 之間 Alice 所能獲得的最高分
dp = [[0]*n for _ in range(n)]
# 3. 動態規畫
for length in range(2, n+1): # 區間長度 2 ~ n
for i in range(0, n - length + 1): # 起點 0 ~ n - length
j = i + length - 1 # 終點
for k in range(i, j): # 分割點 i ~ j-1
lsum = psum[k+1] - psum[i] # stoneValue[i] ~ stoneValue[k]
rsum = psum[j+1] - psum[k+1] # stoneValue[k+1] ~ stoneValue[j]
if lsum > rsum: # 左半邊總分較多，剩下右半邊
dp[i][j] = max(dp[i][j], rsum + dp[k+1][j])
elif lsum < rsum: # 右半總分較多，剩下左半邊
dp[i][j] = max(dp[i][j], lsum + dp[i][k])
else: # 兩側分數相同，Alice 選 dp 區間較高分
dp[i][j] = max(dp[i][j], lsum + max(dp[i][k], dp[k+1][j]))
# 答案在 dp[0][n-1]
return dp[0][n-1]
方法2，Runtime: 619 ms, beats 77.25%. Memory: 33.17 MB, beats 65.49%.
class Solution:
def stoneGameV(self, stoneValue: List[int]) -> int:
n = len(stoneValue) # 數量
# 1. 建立前綴和，之後可以用來查詢區間和
psum = [0] * (n+1) # pusm 的索引值比 stoneValue 多 1
for i in range(1, n+1):
psum[i] = psum[i-1] + stoneValue[i-1]
# 2. 建立動態規畫陣列
# dp[i][j] 代表在區間 [i...j] 之間 Alice 所能獲得的最高分
dp = [[0]*n for _ in range(n)]
# lmax[i][j] = dp[i][k] + sum(dp[i:k+1]) 的最大值
lmax = [[0]*n for _ in range(n)]
# rmax[i][j] = dp[k][j] + sum(dp[k:j+1]) 的最大值
rmax = [[0]*n for _ in range(n)]
# 初始化 lmax, rmal，長度 1
for i in range(n):
lmax[i][i] = stoneValue[i]
rmax[i][i] = stoneValue[i]
# 3. 動態規畫，由短至長
for i in range(n-1, -1, -1): # i = n-1 ~ 0
mid = i - 1 # 分割點
for j in range(i+1, n): # j = i+1 ~ n-1
total = psum[j+1] - psum[i] # stoneValue[i] + ... + stoneValue[j]
# 找出左半邊和 L 大於右半邊和 R 的分割點
# 如果 mid + 1 這格還是不符合條件，再向右移動1格
# L >= R => L + L >= L + R => 2*L >= total
# 2 * (psum[mid + 2] - psum[i]) >= total
while mid + 1 < j and 2 * (psum[mid + 2] - psum[i]) <= total:
mid += 1
res = 0
# 狀況1，左半邊總分 > 右半邊總分
if mid >= i:
res = max(res, lmax[i][mid])
# mid 左半邊總分 == 右半邊總分，可以留下右半邊
if 2 * (psum[mid + 1] - psum[i]) == total:
res = max(res, rmax[mid + 1][j])
# 狀況2，左半邊總分 < 右半邊總分
if mid + 2 <= j:
res = max(res, rmax[mid + 2][j])
# 更新 dp, lmax, rmax
dp[i][j] = res
lmax[i][j] = max(lmax[i][j-1], dp[i][j] + total)
rmax[i][j] = max(rmax[i+1][j], dp[i][j] + total)
# 答案在 dp[0][n-1]
return dp[0][n-1]
