题目描述
思路解析
一句话答案：LeetCode 2017 网格游戏：2 行网格里机器人一先走清零、机器人二捡剩下，路径形状就是选一列下拐，枚举拐点用前缀和后缀和算 max(上排后缀, 下排前缀) 取最小，时间 O(n)、空间 O(1)。
两行网格里的机器人博弈，到底在求什么
grid 是 2 行 n 列，每格写着点数。两个机器人先后从左上角 (0,0) 走到右下角 (1,n-1)，每步只能向右或向下。机器人一先走，收走沿途点数、把格子清零；机器人二再走，收走剩下的。机器人一想让机器人二拿得尽量少，机器人二想让自己拿得尽量多，两边都最优，问机器人二拿多少。题面上排是 3、1、2、5，下排是 4、2、1、2，答案 6。
两边都要最优，是不是得把走法两两配对推演
两个机器人各自求最优，乍看像要把机器人一走法和机器人二应对两两摆到一起推演，组合一多就压不住。路径其实没几种：只能向右或向下，任何一条从 (0,0) 到 (1,n-1) 的路都长一个样——上排往右走到某一列，在那列往下拐进下排，再沿下排走到底。机器人一真正能决定的，只有在哪一列下拐，一共就 n 种选择。
拐点一定下来，机器人二只够得着两块残料
机器人一沿某列下拐、清零整条路后，没被碰过的只剩两块：上排拐点右边的一段，和下排拐点左边的一段。机器人二同样只能向右向下走，一旦下拐就回不到上排，这两块没法都要，只能挑点数大的一块。
于是机器人二在这一列能拿到的，就是 max(上排拐点右段之和, 下排拐点左段之和)。前者是从拐点右边加到头的后缀和，后者是从最左加到拐点左边的前缀和——前缀和、后缀和，就是从头、从尾累加起来的跑动总和。机器人一要做的，是在所有拐点里让较大者尽量小，逐列取最小。
用一前一后两个滚动和，一趟就扫完
不必每列都把两段重新加一遍。参考代码里 s1 先存上排整行的和，s2 从 0 起。从左往右枚举拐点列时，先让 s1 减掉上排当前这个数，s1 就变成上排后缀和；此刻 s2 恰好是下排前缀和；拿 max(s1, s2) 更新答案后，再把 s2 加上下排当前这个数，留给下一列。一列只做减、比、加各一次，走完就是 O(n)。
拿题面的 3、1、2、5 和 4、2、1、2 逐列走一遍
上排总和 11 先当作 s1,s2 从 0 起。拐第 0 列：s1 减 3 变 8,s2 还是 0，较大者 8，答案记 8;s2 加 4 变 4。拐第 1 列：s1 减 1 变 7,s2 是 4，较大者 7，答案更新成 7;s2 加 2 变 6。
拐第 2 列：s1 减 2 变 5,s2 是 6，较大者取 6，答案更新成 6;s2 加 1 变 7。拐第 3 列：s1 减 5 变 0,s2 是 7，较大者 7，不比 6 小，答案仍是 6。四列下来，机器人一拐第 2 列把对手压到 6，即最终答案。
别把拐点列算进残料，也别用 int 接总和
复杂度先交代：求一次上排和是 O(n)，枚举 n 个拐点每列常数步，时间 O(n)，只用几个滚动变量，空间 O(1)。剩下几处提前避开。拐点那一列上下两格都被机器人一收走，上排后缀从它右边一列起、下排前缀到它左边一列止，归错边就多算一格。点数总和能到五十亿、越过 int 上限，C 加加 用 long long、Java 用 long,int 会溢出成负数。n 为 1 时上下都没有残料，机器人二只能拿 0。最容易想歪的，是把机器人二所得当成两块之和——路径不能回头，较大者才是它真拿到的。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
记住这一句:机器人一挑一列往下拐,机器人二就只能在上排右段和下排左段里挑较大的一块拿走。机器人一要做的,是让这个较大值尽量小。下面我们从头把这张图看明白,再逐列试拐点。
先看整张网格 · 两个机器人的起点和终点：这是我们的舞台,一张 2 行 4 列的网格。上排四个数是 3、1、2、5,下排是 4、2、1、2。两个机器人都从左上角 (0,0) 出发,一路只能向右或向下,最后都要走到右下角 (1,3)。先记住这些点数的位置,尤其上排最右边那个 5 和下排的 4,后面它们是胜负手。
机器人一的路径形状 · 上排走一段就下拐：先看机器人一能走成什么样。因为只能向右或向下,它的路一定是:上排从头往右走到某一列,在那一列往下拐一格,再沿下排走到底。这里拿拐点在第 1 列举个样子,紫色两格就是往下拐的地方,灰色就是它走过并清零的整条路。换个拐点,灰色路径就跟着变。机器人一要挑的,正是这个拐点列。
机器人二只剩两块残料 · 二选一：机器人一走完清零后,轮到机器人二。它眼前只剩两块没被清掉的:绿色是上排拐点右边那一段,橙色是下排拐点左边那一段。关键在于,机器人二也只能向右向下走,一旦下拐就回不到上排,所以这两块它没法都拿,只能挑一块。它当然挑点数大的那块。机器人一要做的,就是选个拐点让这较大的一块尽量小。
试拐点第 0 列 · 机器人一吃掉灰色路径：现在试机器人一在第 0 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 0 列,再下排从第 0 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
上排残料 · 第 1 列起的一段：先看绿色这块,上排拐点右边、从第 1 列起的一段:1 加 2 加 5,一共 8。机器人二要想拿它,就得在上排一直走到底再下拐。这个数记成 topSuffix,等于 8。
下排残料 · 第 0 列前的一段：拐点就在第 0 列,下排左边没有格子留下,这块是空的,bottomPrefix 等于 0。机器人二在下排这一侧什么也捡不到。
机器人二取较大块 = 8 · 更新最优：机器人二在两块里挑大的:上排后缀 8 和下排前缀 0,较大的是 8,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 0 列,机器人二会拿到 8。把它和之前的最优比一比,目前机器人一能把对手压到最少 8。
试拐点第 1 列 · 机器人一吃掉灰色路径：现在试机器人一在第 1 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 1 列,再下排从第 1 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
上排残料 · 第 2 列起的一段：先看绿色这块,上排拐点右边、从第 2 列起的一段:2 加 5,一共 7。机器人二要想拿它,就得在上排一直走到底再下拐。这个数记成 topSuffix,等于 7。
下排残料 · 第 1 列前的一段：再看橙色这块,下排拐点左边、前 1 列的一段:4,一共 4。机器人二要想拿它,就得一开始就下拐、沿下排走。这个数记成 bottomPrefix,等于 4。
机器人二取较大块 = 7 · 更新最优：机器人二在两块里挑大的:上排后缀 7 和下排前缀 4,较大的是 7,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 1 列,机器人二会拿到 7。把它和之前的最优比一比,目前机器人一能把对手压到最少 7。
试拐点第 2 列 · 机器人一吃掉灰色路径：现在试机器人一在第 2 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 2 列,再下排从第 2 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
上排残料 · 第 3 列起的一段：先看绿色这块,上排拐点右边、从第 3 列起的一段:5,一共 5。机器人二要想拿它,就得在上排一直走到底再下拐。这个数记成 topSuffix,等于 5。
下排残料 · 第 2 列前的一段：再看橙色这块,下排拐点左边、前 2 列的一段:4 加 2,一共 6。机器人二要想拿它,就得一开始就下拐、沿下排走。这个数记成 bottomPrefix,等于 6。
机器人二取较大块 = 6 · 更新最优：机器人二在两块里挑大的:上排后缀 5 和下排前缀 6,较大的是 6,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 2 列,机器人二会拿到 6。把它和之前的最优比一比,目前机器人一能把对手压到最少 6。
试拐点第 3 列 · 机器人一吃掉灰色路径：现在试机器人一在第 3 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 3 列,再下排从第 3 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
上排残料 · 第 4 列起的一段：拐点已经是最后一列了,上排右边没有格子留下,这块是空的,topSuffix 等于 0。机器人二在上排这一侧什么也捡不到。
下排残料 · 第 3 列前的一段：再看橙色这块,下排拐点左边、前 3 列的一段:4 加 2 加 1,一共 7。机器人二要想拿它,就得一开始就下拐、沿下排走。这个数记成 bottomPrefix,等于 7。
机器人二取较大块 = 7 · 更新最优：机器人二在两块里挑大的:上排后缀 0 和下排前缀 7,较大的是 7,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 3 列,机器人二会拿到 7。把它和之前的最优比一比,目前机器人一能把对手压到最少 6。
最优拐点在第 2 列 · 机器人二只拿 6：四种拐法全试完了:拐第 0 列对方拿 8,第 1 列拿 7,第 2 列拿 6,第 3 列拿 7。机器人一当然选让对手最少的那个,也就是拐第 2 列,把机器人二死死压在 6。你看这一拐很妙,机器人一把上排右段压到只剩一个 5,而下排前面 4 加 2 等于 6 更大,所以机器人二只能拿这 6。
回放 · 枚举拐点取 max 的最小值：回顾整个思路:机器人一的路径就是选一列往下拐,拐完给机器人二留下上排右段和下排左段两块残料,机器人二只能二选一拿较大的。我们逐列枚举拐点,每列算出 max(上排后缀, 下排前缀),再取所有列里最小的那个,就是机器人二在双方都最优时拿到的点数,这张图上是 6。真正写代码时,前缀后缀都能一边扫一边增减维护,不用每列重新求和。
边界要点:n 为 1 时对手拿 0;拐点吃掉大数常常最优;上排后缀与下排前缀都严格不含拐点列。
面试重点:路径即选拐点、前缀后缀滚动做到 O(n)、机器人二取 max 且注意 C 加加 用 long long、Java 用 long 防溢出。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def gridGame(self, grid: List[List[int]]) -> int: ans = inf s1, s2 = sum(grid[0]), 0 for j, v in enumerate(grid[0]): s1 -= v ans = min(ans, max(s1, s2)) s2 += grid[1][j] return ans复杂度
- 时间：O(n)，先求一次上排和是 O(n),再从左到右枚举 n 个拐点列,每列只做减一个数、比一次大小、加一个数这几步常数操作,总共随列数 n 线性增长
- 空间：O(1)，只用了 s1、s2、答案这几个变量滚动维护前缀和与后缀和,不额外开数组,占用是常数,不随 n 变化
易错点
面试追问把动画讲成自己的话
追问这题的核心观察是什么?
追问怎么把它做到线性?
追问有哪些容易出错的细节?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
获取单值网格的最小操作数
LeetCode 2033 · 中等 · 沿着 图论套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题