日期：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)
C++ 程式碼
方法1。Runtime: 98 ms, beats 83.46%. Memory: 91.68 MB, beats 72.18%.
class Solution {
public:
int stoneGameVIII(vector<int>& stones) {
/* 1. 建立前綴和陣列 */
int n = (int)stones.size();
vector<int> psum (stones.begin(), stones.end());
for(int i = 1; i < n; i++) {
psum[i] += psum[i-1];
}
/* 2. 動態規畫，由最後一個狀態往回推 */
int dp = psum[n-1];
for(int i = n-2; i > 0; i--) {
dp = max(psum[i] - dp, dp);
}
return dp;
}
};
方法2。Runtime: 109 ms, beats 51.39%. Memory: 99.96 MB, beats 30.75%.
class Solution {
public:
int n;
vector<int> memo;
/* dfs 函式 */
int dfs(int i, const vector<int>& psum) {
// 遞迴出口，i = n-1，全拿
if (i == n-1) {
return psum[n-1];
}
// 如果 memo 之中有已經計算過的值，直接回傳
if (memo[i] != -1) {
return memo[i];
}
// 遞迴，選擇 take 及 skip 較大者
int skip = dfs(i+1, psum);
int take = psum[i] - skip;
memo[i] = max(take, skip);
return memo[i];
}
int stoneGameVIII(vector<int>& stones) {
/* 1. 建立前綴和陣列 */
n = (int)stones.size();
vector<int> psum (stones.begin(), stones.end());
for(int i = 1; i < n; i++) {
psum[i] += psum[i-1];
}
/* 2. 記憶化與遞迴 */
memo.assign(n, -1);
return dfs(1, psum);
}
};
C 語言程式碼
方法1。Runtime: 98 ms, beats 60.00%. Memory: 16.46 MB, beats 80.00%.
int stoneGameVIII(int* stones, int stonesSize){
/* 1. 建立前綴和陣列 */
int psum[100001] = {0};
psum[0] = stones[0];
for(int i = 1; i < stonesSize; i++) {
psum[i] = psum[i-1] + stones[i];
}
/* 2. 動態規畫，由最後一個狀態往回推 */
int dp = psum[stonesSize-1];
for(int i = stonesSize-2; i > 0; i--) {
int take = psum[i] - dp;
int skip = dp;
if (take > skip) dp = take;
else dp = skip;
}
return dp;
}
方法2。Runtime: 116 ms, beats -%. Memory: 21.78 MB, beats 60.00%.
int n, psum[100001], memo[100001];
int dfs(int i) {
if (i == n-1) {
return psum[n-1];
}
if (memo[i] != -1) {
return memo[i];
}
int skip = dfs(i+1);
int take = psum[i] - skip;
if (take > skip) memo[i] = take;
else memo[i] = skip;
return memo[i];
}
int stoneGameVIII(int* stones, int stonesSize){
/* 1. 建立前綴和陣列 */
n = stonesSize;
memset(psum, 0, sizeof(psum));
psum[0] = stones[0];
for(int i = 1; i < n; i++) {
psum[i] = psum[i-1] + stones[i];
}
/* 2. 記憶化與遞迴 */
memset(memo, -1, sizeof(memo));
return dfs(1);
}
沒有留言:
張貼留言