Alice 和 Bob 輪流從一排石頭的兩端取石頭，Alice 先手。每次只能取最左或最右的一堆，取到石頭總數多的人獲勝。假設兩人都最優策略，判斷 Alice 是否一定贏。
Example:
Input: piles = [5,3,4,5] Output: true
Intuition
TIP
區間 DP：dp[i][j] 表示在 piles[i..j] 中先手能比後手多拿多少。
- 數學上 Alice 必勝（石頭數為偶數，Alice 可以選擇只拿奇數位或偶數位的所有石頭）
- 但通用的區間 DP 解法適用於更一般的情況
dp[i][j] = max(piles[i] - dp[i+1][j], piles[j] - dp[i][j-1])
Approaches
1. Interval DP — O(n^2) / O(n^2)
- Idea:
dp[i][j]代表面對piles[i..j]時，當前玩家能比對手多拿的分數。選左端則得piles[i] - dp[i+1][j]，選右端則得piles[j] - dp[i][j-1]。 - Time:
O(n^2) - Space:
O(n^2)
class Solution {
fun stoneGame(piles: IntArray): Boolean {
val n = piles.size
val dp = Array(n) { IntArray(n) }
for (i in 0 until n) dp[i][i] = piles[i]
for (len in 2..n) {
for (i in 0..n - len) {
val j = i + len - 1
dp[i][j] = maxOf(piles[i] - dp[i + 1][j], piles[j] - dp[i][j - 1])
}
}
return dp[0][n - 1] > 0
}
}⭐ 2. Math (Constant Time) — O(1) / O(1)
- Idea: 石頭堆數為偶數，Alice 可以選擇拿所有奇數位置或所有偶數位置的石頭。由於總和為奇數（題目保證），必有一邊更大，Alice 必勝。
- Time:
O(1) - Space:
O(1)
class Solution {
fun stoneGame(piles: IntArray): Boolean {
return true
}
}🔑 Takeaways
- Pattern: 博弈型區間 DP —
dp[i][j]表示先手相對優勢 - Key trick: 此題有數學必勝解，但區間 DP 解法是更通用的博弈策略模板（適用於 Stone Game 系列）