Alice 和 Bob 輪流從石頭堆的開頭取石頭，Alice 先手。每次可以取前
1到2M堆石頭，取X堆後M更新為max(M, X)。初始M = 1。兩人都最優策略，回傳 Alice 能拿到的最多石頭數。
Example:
Input: piles = [2,7,9,4,4] Output: 10
Intuition
TIP
記憶化搜索：dp[i][m] 表示從第 i 堆開始、當前 M 值為 m 時，當前玩家能拿到的最多石頭數。
- 使用後綴和來快速計算從第
i堆到最後的石頭總和 - 當前玩家取
x堆後，對手能拿到dp[i+x][max(m,x)] - 當前玩家拿到
suffixSum[i] - dp[i+x][max(m,x)] - 取所有
x中最大的結果
Approaches
1. Memoized Search — O(n^3) / O(n^2)
- Idea: Top-down DFS + 記憶化，
dfs(i, m)回傳從第i堆開始、M 為m時，當前玩家的最大收穫。 - Time:
O(n^3) - Space:
O(n^2)
class Solution {
fun stoneGameII(piles: IntArray): Int {
val n = piles.size
val suffixSum = IntArray(n + 1)
for (i in n - 1 downTo 0) suffixSum[i] = suffixSum[i + 1] + piles[i]
val memo = Array(n) { IntArray(n + 1) { -1 } }
fun dfs(i: Int, m: Int): Int {
if (i >= n) return 0
if (i + 2 * m >= n) return suffixSum[i]
if (memo[i][m] != -1) return memo[i][m]
var best = 0
for (x in 1..2 * m) {
best = maxOf(best, suffixSum[i] - dfs(i + x, maxOf(m, x)))
}
memo[i][m] = best
return best
}
return dfs(0, 1)
}
}⭐ 2. Bottom-up DP — O(n^3) / O(n^2)
- Idea: 從後往前填表，
dp[i][m]表示從第i堆開始、M 為m時，當前玩家能拿到的最大石頭數。 - Time:
O(n^3) - Space:
O(n^2)
class Solution {
fun stoneGameII(piles: IntArray): Int {
val n = piles.size
val suffixSum = IntArray(n + 1)
for (i in n - 1 downTo 0) suffixSum[i] = suffixSum[i + 1] + piles[i]
val dp = Array(n + 1) { IntArray(n + 1) }
for (i in n - 1 downTo 0) {
for (m in 1..n) {
if (i + 2 * m >= n) {
dp[i][m] = suffixSum[i]
} else {
for (x in 1..2 * m) {
dp[i][m] = maxOf(dp[i][m], suffixSum[i] - dp[i + x][maxOf(m, x)])
}
}
}
}
return dp[0][1]
}
}🔑 Takeaways
- Pattern: 博弈 DP + 後綴和 — 「我拿的 = 總和 - 對手拿的」
- Key trick: 後綴和讓計算剩餘石頭總和變成 O(1)；博弈問題中「最大化自己 = 最小化對手」