2017. Grid Game

Medium

Description

給定 2 x n 的矩陣 grid，兩個機器人都從 (0,0) 出發到 (1,n-1)，只能向右或向下移動。第一個機器人先走，經過的格子歸零；第二個機器人再走，收集剩餘的點數。第一個機器人要最小化第二個機器人的得分，第二個機器人會最大化自己的得分。回傳第二個機器人的得分。

Example:

Input: grid = [[2,5,4],[1,5,1]] Output: 4 （第一個機器人選擇在 column 2 轉下，第二個機器人最多只能得到 4）

Intuition#

核心思路：第一個機器人一定在某個 column c 從第 0 行轉到第 1 行。轉折點確定後，第二個機器人只能選擇「第 0 行 c 右邊的部分」或「第 1 行 c 左邊的部分」中較大的那個。第一個機器人要最小化這個最大值。

第一個機器人的路徑形狀：沿第 0 行走到某個 column c，轉下到第 1 行，再走到底
轉折後，第二個機器人的可選區域只有兩塊：上方的 suffix sum（column c+1 到 n-1）和下方的 prefix sum（column 0 到 c-1）
第二個機器人會取兩者的 max，第一個機器人要找使 max 最小的 c

Approaches#

1: Brute Force Prefix Sum#

概念: 預計算前綴和，枚舉每個轉折點 c，計算兩塊區域的和，取 max 後找全局 min
時間複雜度: O(n) - 前綴和 + 一次遍歷
空間複雜度: O(n) - 前綴和陣列

class Solution {
    fun gridGame(grid: Array<IntArray>): Long {
        val n = grid[0].size
        val topPrefix = LongArray(n + 1)
        val botPrefix = LongArray(n + 1)

        for (i in 0 until n) {
            topPrefix[i + 1] = topPrefix[i] + grid[0][i]
            botPrefix[i + 1] = botPrefix[i] + grid[1][i]
        }

        var result = Long.MAX_VALUE
        for (c in 0 until n) {
            val topRemaining = topPrefix[n] - topPrefix[c + 1]  // 第 0 行 c+1..n-1
            val botRemaining = botPrefix[c]                      // 第 1 行 0..c-1
            val robot2Score = maxOf(topRemaining, botRemaining)
            result = minOf(result, robot2Score)
        }
        return result
    }
}

⭐2: Running Sum (O(1) Space)#

概念: 不需要額外陣列，用 running sum 即時計算：topSum 初始化為第 0 行總和，botSum 初始化為 0，遍歷每個轉折點時更新
時間複雜度: O(n) - 一次遍歷
空間複雜度: O(1) - 只用常數變數

class Solution {
    fun gridGame(grid: Array<IntArray>): Long {
        val n = grid[0].size
        var topSum = 0L
        for (v in grid[0]) topSum += v

        var botSum = 0L
        var result = Long.MAX_VALUE

        for (c in 0 until n) {
            topSum -= grid[0][c]         // 第 0 行 c 右邊的 suffix sum
            val robot2Score = maxOf(topSum, botSum)
            result = minOf(result, robot2Score)
            botSum += grid[1][c]         // 第 1 行 c 左邊的 prefix sum
        }

        return result
    }
}

這題的陷阱是不能用 Greedy 讓第一個機器人走最大路徑。第一個機器人的目標是最小化對手的得分，不是最大化自己的得分。必須考慮轉折點對剩餘區域的影響。

🔑 Takeaways#

Pattern: 2-row grid 的博弈問題 -> 轉折點枚舉 + Prefix/Suffix Sum
關鍵技巧: 理解第一個機器人的轉折決定了第二個機器人的可選區域，問題轉化為 min-max 優化；注意使用 Long 避免 overflow