1140. Stone Game II

Medium

Description

Alice 和 Bob 輪流從石頭堆的開頭取石頭，Alice 先手。每次可以取前 1 到 2M 堆石頭，取 X 堆後 M 更新為 max(M, X)。初始 M = 1。兩人都最優策略，回傳 Alice 能拿到的最多石頭數。

Example:

Input: piles = [2,7,9,4,4] Output: 10

Intuition#

記憶化搜索：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: 記憶化搜索#

概念: Top-down DFS + 記憶化，dfs(i, m) 回傳從第 i 堆開始、M 為 m 時，當前玩家的最大收穫。
時間複雜度: O(n^3)
空間複雜度: 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#

概念: 從後往前填表，dp[i][m] 表示從第 i 堆開始、M 為 m 時，當前玩家能拿到的最大石頭數。
時間複雜度: O(n^3)
空間複雜度: 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 + 後綴和 — 「我拿的 = 總和 - 對手拿的」
關鍵技巧: 後綴和讓計算剩餘石頭總和變成 O(1)；博弈問題中「最大化自己 = 最小化對手」