2017. Grid Game

Grid Game

題目描述： 給定一個 2 x n 的網格 grid，兩個機器人從左上角 (0,0) 出發到右下角 (1,n-1)，只能向右或向下移動。第一個機器人先走，走過的格子歸零。第二個機器人接著走，收集剩餘的分數。第一個機器人的目標是最小化第二個機器人能獲得的分數。求第二個機器人在最優策略下能獲得的最大分數（即第一個機器人最優時的結果）。

解題思路：

1. 第一個機器人的路徑必定是：在某一列 j 從第 0 行向下到第 1 行，之後一直向右。
2. 第一個機器人走完後，第二個機器人只能選擇兩種有價值的路徑：
   • 全走第 0 行：收集 grid[0][j+1] + ... + grid[0][n-1]（第一個機器人未走的第 0 行後段）
   • 全走第 1 行：收集 grid[1][0] + ... + grid[1][j-1]（第一個機器人未走的第 1 行前段）
3. 第二個機器人會選這兩者中較大的。
4. 第一個機器人要最小化這個最大值。
5. 用前綴和（或後綴和）枚舉每個轉折點 j，O(n) 即可解決。

時間複雜度：O(n) — 一次遍歷計算所有轉折點。

空間複雜度：O(1) — 僅使用常數額外空間。

前綴和陣列法 O(n)：預先計算兩行的前綴和陣列，然後枚舉轉折點。邏輯相同，但使用 O(n) 額外空間儲存前綴和。

二分搜尋法 O(n log S)：二分答案 S，檢查是否存在轉折點使第二個機器人得分不超過 S。但由於直接枚舉已是 O(n)，二分搜尋並無優勢。

1. 如果網格擴展為 m x n（多行），問題變成怎樣？還能用類似方法嗎？
2. 如果有三個機器人依序走，問題如何建模？
3. 為什麼第二個機器人的最優路徑一定是全走第 0 行後段或全走第 1 行前段，而不是混合路徑？