Intuition#

區間 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: 區間 DP#

• 概念: dp[i][j] 代表面對 piles[i..j] 時，當前玩家能比對手多拿的分數。選左端則得 piles[i] - dp[i+1][j]，選右端則得 piles[j] - dp[i][j-1]。
• 時間複雜度: O(n^2)
• 空間複雜度: 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: 數學解（常數時間）#

• 概念: 石頭堆數為偶數，Alice 可以選擇拿所有奇數位置或所有偶數位置的石頭。由於總和為奇數（題目保證），必有一邊更大，Alice 必勝。
• 時間複雜度: O(1)
• 空間複雜度: O(1)

class Solution {
    fun stoneGame(piles: IntArray): Boolean {
        return true
    }
}

🔑 Takeaways#

• Pattern: 博弈型區間 DP — dp[i][j] 表示先手相對優勢
• 關鍵技巧: 此題有數學必勝解，但區間 DP 解法是更通用的博弈策略模板（適用於 Stone Game 系列）