3148. 矩阵中的最大得分

发表于 2026-01-15 分类于力扣阅读次数： Waline：本文字数： 1.2k 阅读时长 ≈ 4 分钟

考点

子矩形DP

思路

1. 问题抽象

给定一个 \(n \times m\) 的整数矩阵 \(a\)。

可以从任意格子作为起点
每一步可以：
- 向右（同一行，列号增大）
- 向下（同一列，行号增大）
从格子 \(u\) 移动到 \(v\) 的得分为 \[ a[v] - a[u] \]
要求路径至少包含一次移动
目标：最大化路径总得分

2. 关键观察（得分的“望远镜效应”）

设路径经过的格子依次为： \[ p_0 \rightarrow p_1 \rightarrow \cdots \rightarrow p_k \] 总得分为： \[ (a[p_1]-a[p_0]) + (a[p_2]-a[p_1]) + \cdots + (a[p_k]-a[p_{k-1}]) \] 中间项完全抵消，得到： \[ \text{score} = a[p_k] - a[p_0] \] 结论：

路径形状、长度、中间节点全部无关
得分只取决于：
- 起点值
- 终点值

3. 可达性约束

若终点为 \((i,j)\)，则起点 \((x,y)\) 必须满足： \[ x \le i,\quad y \le j,\quad (x,y)\neq(i,j) \] 即：起点来自终点的左上可达区域。

4. 建模方式一：左上区域最小值（前缀最小 DP）

4.1 状态定义

令： \[ f[i][j] = \min \{ a[x][y] \mid 1 \le x \le i,\ 1 \le y \le j \} \] 即左上矩形区域内的最小格子值。

4.2 状态转移

对终点 \((i,j)\)，最优起点来自：

上方区域：\(f[i-1][j]\)
左方区域：\(f[i][j-1]\)

因此： \[ \text{bestStart} = \min(f[i-1][j], f[i][j-1]) \] 若存在合法起点，则： \[ \text{answer} = \max(\text{answer},\ a[i][j] - \text{bestStart}) \] 并更新前缀最小： \[ f[i][j] = \min(\text{bestStart},\ a[i][j]) \]

4.3 对应 AC 代码（二维 DP）

class Solution {
public:
    int neg = INT_MIN >> 1, inf = INT_MAX >> 1;

    int maxScore(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        // f[i][j] 表示左上矩形 (1..i,1..j) 内的最小格子值
        vector<vector<int>> f(n + 1, vector<int>(m + 1, inf));
        int ans = neg;

        for (int i = 1; i <= n; ++i) {
            for (int j = 1; j <= m; ++j) {
                int mi = inf;
                // 起点来自上方
                if (i > 1) mi = min(mi, f[i - 1][j]);
                // 起点来自左方
                if (j > 1) mi = min(mi, f[i][j - 1]);

                // 若存在合法起点，则更新答案
                if (mi != inf)
                    ans = max(ans, grid[i - 1][j - 1] - mi);

                // 更新前缀最小值
                f[i][j] = min(mi, grid[i - 1][j - 1]);
            }
        }
        return ans;
    }
};

5. 建模方式二：同行 / 同列最后一步转移 DP

该建模方式严格遵循：

终点的最后一步只能来自同行左侧或同列上方

5.1 状态定义

令： \[ dp[i][j] = \text{以 }(i,j)\text{ 为终点、至少移动一次的最大得分} \]

5.2 转移推导

若最后一步来自同行左侧 \((i,k)\)： \[ dp[i][j] = dp[i][k] + (a[i][j] - a[i][k]) \] 来自同列上方 \((k,j)\)： \[ dp[i][j] = dp[k][j] + (a[i][j] - a[k][j]) \] 合并并提取 \(a[i][j]\)： \[ dp[i][j] = a[i][j] + \max \Big( \max_{k<j}(dp[i][k]-a[i][k]), \max_{k<i}(dp[k][j]-a[k][j]) \Big) \]

5.3 起点的引入（关键）

起点尚未发生移动，其得分为 \(0\)。

若从起点 \(s\) 直接跳到 \((i,j)\)： \[ \text{score} = a[i][j] - a[s] = a[i][j] + (-a[s]) \] 因此，每个格子 \((i,j)\) 都应贡献： \[ v(i,j) = \max\big(-a[i][j],\ dp[i][j]-a[i][j]\big) \] 作为后续状态的前驱候选。

5.4 一维优化实现

维护：

row：当前行左侧的 \(v\) 前缀最大
col[j]：当前列上方的 \(v\) 前缀最大

5.5 对应 AC 代码（一维 DP）

class Solution {
public:
    int neg = INT_MIN >> 1, inf = INT_MAX >> 1;

    int maxScore(vector<vector<int>>& grid) {
        int n = grid.size(), m = grid[0].size();
        // col[j] 表示第 j 列上方的最大贡献值 v
        vector<int> col(m + 1, neg);
        int ans = neg;

        for (int i = 1; i <= n; ++i) {
            int row = neg; // 当前行左侧的最大贡献值 v
            for (int j = 1; j <= m; ++j) {
                int x = grid[i - 1][j - 1];

                int f = neg;
                // 最后一步来自同行左侧
                if (j > 1) f = max(f, row);
                // 最后一步来自同列上方
                if (i > 1) f = max(f, col[j]);

                // 若存在前驱，更新答案
                int v = -x; // 起点贡献
                if (f != neg) {
                    ans = max(ans, f + x); // dp = f + x
                    v = max(v, f);        // v = max(-x, dp-x)
                }

                // 更新前缀最大
                row = max(row, v);
                col[j] = max(col[j], v);
            }
        }
        return ans;
    }
};

6. 两种建模的等价性说明

方法一直接维护： \[ \min a[\text{左上可达起点}] \]
方法二维护的是： \[ \max(-a[\text{起点}]) \quad\Longleftrightarrow\quad -\min a[\text{起点}] \]

因此最终计算的： \[ a[i][j] - \min a[\text{起点}] \] 在两种 DP 中完全一致。

7. 总结

本题的本质是起点-终点差值最大化
路径结构无关，只剩下可达性约束
可用两种等价 DP 视角：
1. 左上区域前缀最小
2. 同行 / 同列最后一步转移（维护贡献值）

第二种视角在推导复杂 DP 或类似“方向受限图路径”问题时具有更强的扩展性。