解題說明
Grid Game
題目描述：
給定一個 2 x n 的網格 grid，兩個機器人從左上角 (0,0) 出發到右下角 (1,n-1)，只能向右或向下移動。第一個機器人先走，走過的格子歸零。第二個機器人接著走，收集剩餘的分數。第一個機器人的目標是最小化第二個機器人能獲得的分數。求第二個機器人在最優策略下能獲得的最大分數（即第一個機器人最優時的結果）。
解題思路：
- 第一個機器人的路徑必定是：在某一列
j從第 0 行向下到第 1 行，之後一直向右。 - 第一個機器人走完後，第二個機器人只能選擇兩種有價值的路徑：
- 全走第 0 行：收集
grid[0][j+1] + ... + grid[0][n-1]（第一個機器人未走的第 0 行後段） - 全走第 1 行：收集
grid[1][0] + ... + grid[1][j-1]（第一個機器人未走的第 1 行前段）
- 全走第 0 行：收集
- 第二個機器人會選這兩者中較大的。
- 第一個機器人要最小化這個最大值。
- 用前綴和（或後綴和）枚舉每個轉折點
j，O(n) 即可解決。
C++ 解法
複雜度分析
時間複雜度：O(n) — 一次遍歷計算所有轉折點。
空間複雜度：O(1) — 僅使用常數額外空間。
虛擬碼
1. Compute topSuffix = sum of entire row 0 2. Set botPrefix = 0, ans = infinity 3. For each column j from 0 to n-1: a. topSuffix -= grid[0][j] (remaining row 0 after column j) b. robot2Score = max(topSuffix, botPrefix) c. ans = min(ans, robot2Score) d. botPrefix += grid[1][j] (row 1 before column j+1) 4. Return ans
其他解法
前綴和陣列法 O(n)：預先計算兩行的前綴和陣列，然後枚舉轉折點。邏輯相同，但使用 O(n) 額外空間儲存前綴和。
二分搜尋法 O(n log S)：二分答案 S，檢查是否存在轉折點使第二個機器人得分不超過 S。但由於直接枚舉已是 O(n)，二分搜尋並無優勢。
延伸思考
- 如果網格擴展為
m x n（多行），問題變成怎樣？還能用類似方法嗎？ - 如果有三個機器人依序走，問題如何建模？
- 為什麼第二個機器人的最優路徑一定是全走第 0 行後段或全走第 1 行前段，而不是混合路徑？