# 2017. Grid Game
###### tags: `Leetcode` `Medium` `Prefix Sum` `Min-Max Strategy`
Link: https://leetcode.com/problems/grid-game/description/
## 思路
思路参考[这里](https://leetcode.com/problems/grid-game/description/)

重点就在于grid只有两行 所以两个robot都只有一个下降机会

经过观察我们可以发现不管first robot从哪下降 对于second robot来说either在最开始下降or在最后面下降才会得到最optimal的结果

如果在中间下降 分两种情况:
1. 在first robot下降位置前下降 相当于只多了bottom line两个下降位置之间的point 那完全可以在最开始下降
2. 在first robot下降位置后下降 相当于只多了top line两个下降位置之间的point 那完全可以最后面再下降

因此假设first robot选择从point ```i```下去, 那么second robot要么collect ```bottom = sum(grid[1][0] .. grid[1][i-1])```要么collect ```top = sum(grid[0][i+1] ... grid[0][n-1])```

所以其实就相当于first robot 要minimize top和bottom的最大值
## Code

class Solution:
    def gridGame(self, grid: List[List[int]]) -> int:
        top, bottom, res = sum(grid[0]), 0, math.inf
        for g0, g1 in zip(grid[0], grid[1]):
            top -= g0
            res = min(res, max(top, bottom))
            bottom += g1
        return res