MediumRating 2035
1140. Stone Game II
arraymathdynamic-programmingprefix-sumgame-theory
解題說明
Stone Game II
題目描述：
有一排石頭堆 piles。Alice 和 Bob 輪流取石頭，Alice 先手。每次玩家可以取前 1 到 2M 堆石頭（M 初始為 1），取完後 M = max(M, X)（X 為這次取的堆數）。兩人都以最優策略遊戲，求 Alice 能取到的最大石頭數。
解題思路： 記憶化搜尋 + 前綴和：
定義 dp[i][m] = 從第 i 堆開始、當前 M 值為 m 時，當前玩家（不論是誰）能取到的最大石頭數。
由於是零和遊戲，當前玩家取 suffixSum[i] - dp[i + x][max(m, x)] 的最大值。
轉移：
dp[i][m] = max over x in [1, 2m] of:
suffixSum[i] - dp[i + x][max(m, x)]
直覺：當前玩家取走 x 堆後，對手在剩餘石頭中能取的最大值為 dp[i+x][max(m,x)]，所以當前玩家獲得 suffixSum[i] - dp[i+x][max(m,x)]。
C++ 解法
複雜度分析
時間複雜度：O(n^3) — 三重迴圈：i 有 n 種、m 有 n 種、x 最多 2m 種。實際上 x 的總和受 n 約束。
空間複雜度：O(n^2) — DP 陣列和前綴和陣列。
虛擬碼
1. Compute suffix sums: suffix[i] = sum of piles[i..n-1].
2. Initialize dp[n+1][n+1] = 0.
3. For i from n-1 down to 0:
For m from 1 to n:
For x from 1 to min(2*m, n-i):
dp[i][m] = max(dp[i][m], suffix[i] - dp[i+x][max(m, x)]).
4. Return dp[0][1].其他解法
記憶化搜尋：O(n^3) 時間、O(n^2) 空間。用遞迴 + memo 替代迭代 DP。對許多人來說更直觀，因為遊戲的遞迴結構天然適合自頂向下。
Alpha-Beta 剪枝：在搜尋過程中加入剪枝，跳過不可能產生更好結果的分支。實際效能取決於堆的分佈，最差仍為 O(n^3)。
延伸思考
- 為什麼
suffixSum[i] - dp[i+x][max(m,x)]就是當前玩家的最大收益？這個零和遊戲的性質如何保證正確性？ - M 的上界為什麼是 n？在什麼情況下 M 會增長到 n？
- 如果改為三個玩家輪流取石頭（三人零和遊戲），DP 的狀態和轉移需要如何修改？