网格游戏 图解题解

这道题到底在问什么

输入

grid=[[3,1,2,5],[4,2,1,2]]

输出

6

输入

grid=[[2,5,4],[1,5,1]]

输出

4

先想最直接的笨办法

回顾整个思路:机器人一的路径就是选一列往下拐,拐完给机器人二留下上排右段和下排左段两块残料,机器人二只能二选一拿较大的。我们逐列枚举拐点,每列算出 max(上排后缀, 下排前缀),再取所有列里最小的那个,就是机器人二在双方都最优时拿到的点数,这张图上是 6。真正写代码时,前缀后缀都能一边扫一边增减维护,不用每列重新求和。（动画第 24 步）

最优解：一步一步想明白

1. 3记住这一句:机器人一挑一列往下拐,机器人二就只能在上排右段和下排左段里挑较大的一块拿走。机器人一要做的,是让这个较大值尽量小。下面我们从头把这张图看明白,再逐列试拐点。
2. 4看清网格这是我们的舞台,一张 2 行 4 列的网格。上排四个数是 3、1、2、5,下排是 4、2、1、2。两个机器人都从左上角 (0,0) 出发,一路只能向右或向下,最后都要走到右下角 (1,3)。先记住这些点数的位置,尤其上排最右边那个 5 和下排的 4,后面它们是胜负手。
3. 5路径 = 上排一段加下排一段先看机器人一能走成什么样。因为只能向右或向下,它的路一定是:上排从头往右走到某一列,在那一列往下拐一格,再沿下排走到底。这里拿拐点在第 1 列举个样子,紫色两格就是往下拐的地方,灰色就是它走过并清零的整条路。换个拐点,灰色路径就跟着变。机器人一要挑的,正是这个拐点列。
4. 6两块残料取其大机器人一走完清零后,轮到机器人二。它眼前只剩两块没被清掉的:绿色是上排拐点右边那一段,橙色是下排拐点左边那一段。关键在于,机器人二也只能向右向下走,一旦下拐就回不到上排,所以这两块它没法都拿,只能挑一块。它当然挑点数大的那块。机器人一要做的,就是选个拐点让这较大的一块尽量小。
5. 7拐点第 0 列现在试机器人一在第 0 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 0 列,再下排从第 0 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
6. 8上排后缀 = 8先看绿色这块,上排拐点右边、从第 1 列起的一段:1 加 2 加 5,一共 8。机器人二要想拿它,就得在上排一直走到底再下拐。这个数记成 topSuffix,等于 8。
7. 9下排前缀 = 0拐点就在第 0 列,下排左边没有格子留下,这块是空的,bottomPrefix 等于 0。机器人二在下排这一侧什么也捡不到。
8. 10本列对方拿 8机器人二在两块里挑大的:上排后缀 8 和下排前缀 0,较大的是 8,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 0 列,机器人二会拿到 8。把它和之前的最优比一比,目前机器人一能把对手压到最少 8。
9. 11拐点第 1 列现在试机器人一在第 1 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 1 列,再下排从第 1 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
10. 12上排后缀 = 7先看绿色这块,上排拐点右边、从第 2 列起的一段:2 加 5,一共 7。机器人二要想拿它,就得在上排一直走到底再下拐。这个数记成 topSuffix,等于 7。
11. 13下排前缀 = 4再看橙色这块,下排拐点左边、前 1 列的一段:4,一共 4。机器人二要想拿它,就得一开始就下拐、沿下排走。这个数记成 bottomPrefix,等于 4。
12. 14本列对方拿 7机器人二在两块里挑大的:上排后缀 7 和下排前缀 4,较大的是 7,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 1 列,机器人二会拿到 7。把它和之前的最优比一比,目前机器人一能把对手压到最少 7。
13. 15拐点第 2 列现在试机器人一在第 2 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 2 列,再下排从第 2 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
14. 16上排后缀 = 5先看绿色这块,上排拐点右边、从第 3 列起的一段:5,一共 5。机器人二要想拿它,就得在上排一直走到底再下拐。这个数记成 topSuffix,等于 5。
15. 17下排前缀 = 6再看橙色这块,下排拐点左边、前 2 列的一段:4 加 2,一共 6。机器人二要想拿它,就得一开始就下拐、沿下排走。这个数记成 bottomPrefix,等于 6。
16. 18本列对方拿 6机器人二在两块里挑大的:上排后缀 5 和下排前缀 6,较大的是 6,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 2 列,机器人二会拿到 6。把它和之前的最优比一比,目前机器人一能把对手压到最少 6。
17. 19拐点第 3 列现在试机器人一在第 3 列往下拐。紫色是它下拐的两格,灰色是它走过并清零的整条路:上排从第 0 列到第 3 列,再下排从第 3 列到第 3 列。这些格子机器人二再来时都是 0 了。接下来看它给机器人二留下了哪两块。
18. 20上排后缀 = 0拐点已经是最后一列了,上排右边没有格子留下,这块是空的,topSuffix 等于 0。机器人二在上排这一侧什么也捡不到。
19. 21下排前缀 = 7再看橙色这块,下排拐点左边、前 3 列的一段:4 加 2 加 1,一共 7。机器人二要想拿它,就得一开始就下拐、沿下排走。这个数记成 bottomPrefix,等于 7。
20. 22本列对方拿 7机器人二在两块里挑大的:上排后缀 0 和下排前缀 7,较大的是 7,红色标出的就是它实际拿走的那块。也就是说,机器人一要是拐第 3 列,机器人二会拿到 7。把它和之前的最优比一比,目前机器人一能把对手压到最少 6。
21. 23答案 = 6四种拐法全试完了:拐第 0 列对方拿 8,第 1 列拿 7,第 2 列拿 6,第 3 列拿 7。机器人一当然选让对手最少的那个,也就是拐第 2 列,把机器人二死死压在 6。你看这一拐很妙,机器人一把上排右段压到只剩一个 5,而下排前面 4 加 2 等于 6 更大,所以机器人二只能拿这 6。
22. 24答案 = 6回顾整个思路:机器人一的路径就是选一列往下拐,拐完给机器人二留下上排右段和下排左段两块残料,机器人二只能二选一拿较大的。我们逐列枚举拐点,每列算出 max(上排后缀, 下排前缀),再取所有列里最小的那个,就是机器人二在双方都最优时拿到的点数,这张图上是 6。真正写代码时,前缀后缀都能一边扫一边增减维护,不用每列重新求和。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from __future__ import annotations
from 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

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
using ll = long long;

class Solution {
public:
    long long gridGame(vector<vector<int>>& grid) {
        ll ans = LLONG_MAX;
        int n = grid[0].size();
        ll s1 = 0, s2 = 0;
        for (int& v : grid[0]) s1 += v;
        for (int j = 0; j < n; ++j) {
            s1 -= grid[0][j];
            ans = min(ans, max(s1, s2));
            s2 += grid[1][j];
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public long gridGame(int[][] grid) {
        long ans = Long.MAX_VALUE;
        long s1 = 0, s2 = 0;
        for (int v : grid[0]) {
            s1 += v;
        }
        int n = grid[0].length;
        for (int j = 0; j < n; ++j) {
            s1 -= grid[0][j];
            ans = Math.min(ans, Math.max(s1, s2));
            s2 += grid[1][j];
        }
        return ans;
    }
}

复杂度

面试官可能追问