1406. Stone Game III

Hard
Description

Alice 和 Bob 輪流從石堆陣列的前端取 1、2 或 3 堆石頭。每堆有正或負的分數值。兩人都採最優策略。判斷誰贏或平手。

Example:

Input: stoneValue = [1,2,3,7] Output: “Bob”

Intuition#

博弈 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#

  • 概念: 遞迴嘗試取 1/2/3 堆，記憶化相對分差
  • 時間複雜度: O(n)
  • 空間複雜度: 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)
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 — 用「相對分差」統一雙方的決策，避免分別追蹤兩人的分數
  • 關鍵技巧: dp[i] = max(sum - dp[i+k]) 中的減號反映了雙方的零和博弈；只依賴後三個狀態，可以用模運算滾動