Alice 和 Bob 輪流從石堆陣列的前端取 1、2 或 3 堆石頭。每堆有正或負的分數值。兩人都採最優策略。判斷誰贏或平手。
Example:
Input: stoneValue = [1,2,3,7] Output: “Bob”
Intuition
TIP
博弈 DP：dp[i] 是從索引 i 開始的玩家能獲得的最大「相對分差」。
- 使用「相對分差」的概念：當前玩家得分 - 對手得分
dp[i]= 從第i堆開始，當前玩家能取得的最大分差- 取 k 堆 (k=1,2,3)：分差 =
sum(i..i+k-1) - dp[i+k] dp[i] = max over k of (sum - dp[i+k])
Approaches
1. Top-Down Memoization — O(n) / O(n)
- Idea: 遞迴嘗試取 1/2/3 堆，記憶化相對分差
- Time:
O(n) - Space:
O(n)
class Solution {
fun stoneGameIII(stoneValue: IntArray): String {
val n = stoneValue.size
val memo = IntArray(n) { Int.MIN_VALUE }
fun dp(i: Int): Int {
if (i >= n) return 0
if (memo[i] != Int.MIN_VALUE) return memo[i]
var sum = 0
var best = Int.MIN_VALUE
for (k in 1..3) {
if (i + k - 1 >= n) break
sum += stoneValue[i + k - 1]
best = maxOf(best, sum - dp(i + k))
}
memo[i] = best
return best
}
val diff = dp(0)
return when {
diff > 0 -> "Alice"
diff < 0 -> "Bob"
else -> "Tie"
}
}
}⭐ 2. Bottom-Up DP with Rolling Array — O(n) / O(1)
- Idea: 從後往前計算，只依賴後三個狀態，用滾動變數
- Time:
O(n) - Space:
O(1)
class Solution {
fun stoneGameIII(stoneValue: IntArray): String {
val n = stoneValue.size
// dp[i % 4] 代表從 i 開始的最大分差
val dp = IntArray(4)
for (i in n - 1 downTo 0) {
var sum = 0
var best = Int.MIN_VALUE
for (k in 1..3) {
if (i + k - 1 >= n) break
sum += stoneValue[i + k - 1]
best = maxOf(best, sum - dp[(i + k) % 4])
}
dp[i % 4] = best
}
val diff = dp[0]
return when {
diff > 0 -> "Alice"
diff < 0 -> "Bob"
else -> "Tie"
}
}
}🔑 Takeaways
- Pattern: 博弈 DP — 用「相對分差」統一雙方的決策，避免分別追蹤兩人的分數
- Key trick:
dp[i] = max(sum - dp[i+k])中的減號反映了雙方的零和博弈；只依賴後三個狀態，可以用模運算滾動