当状态住进「行 × 列」的格子里

B 部分的路径型入门已经让我们在网格上走过一次——数字三角形、过河卒，都是「从一格走到相邻一格」。这一节把镜头正式对准二维坐标上的 DP：状态不再是一条链上的 $f[i]$ ，而是一整张表 $dp[i][j]$ ，下标 $(i,j)$ 就是第 $i$ 行第 $j$ 列那个格子。

先划清和 B 路径型的边界：「在网格上数路径条数」这一路（过河卒 $f[i][j]=f[i-1][j]+f[i][j-1]$ 、障碍清零）本质仍是路径计数，入门与例题都放在 B 路径型的过河卒 P1002；本页不再重复计数那一面，而是专注二维状态本身的「形态」——一格的答案由它左 / 上 / 左上邻格的答案「长」出来（最大正方形），以及一张网格上两条路径联合决策（传纸条）。

网格 DP 的通用套路只有一句话：算一格，只回看它的几个「邻居来源」。因为每步只能往固定方向走，任何一格 $(i,j)$ 的最后一步，都只可能从上方 $(i-1,j)$ 、左方 $(i,j-1)$ ，或左上方 $(i-1,j-1)$ 这几格接上来。把「谁能接过来」想清楚，转移就成形了。

本节主问题——「最大正方形」：一张 0/1 矩阵，1 是可用格、0 是空洞，要找出全由 1 组成的最大正方形。图中最大的是一个 3×3 块，边长 3、面积 9。

为什么不直接暴力？枚举正方形的左上角 + 边长再逐格检查是否全 1，最坏是 $O(n^2m^2)$ 甚至更糟——网格一大就崩。网格 DP 的思路，是给每一格算一个「以它为角能撑起多大的正方形」，让相邻格子的答案互相接力，把重复检查压成一次填表。下面就把这个 $dp[i][j]$ 定出来。

最大正方形：三格取 min，短板说了算

定状态。设 $dp[i][j]$ 表示：以 $(i,j)$ 为右下角、全部由 1 组成的最大正方形的边长。为什么钉死「右下角」？因为一个正方形有四个角，但只有右下角能同时「看见」它左边、上边、左上的邻居——正好对应网格 DP 的三个来源，转移最顺。

若 $(i,j)$ 本身是 $0$ ，它当不了任何全 1 正方形的右下角，直接 $dp[i][j]=0$ 。若它是 $1$ ，能撑多大？关键洞察：以 $(i,j)$ 为右下角的正方形，等价于它的上、左、左上三个方向都能撑起「至少一样大」的正方形——任一方向短一截，整体就被拖小。于是取三者的最短板再加自己这一层：

以 (i,j) 为右下角的正方形，被上 dp[i−1][j]、左 dp[i][j−1]、左上 dp[i−1][j−1] 三个方向共同「顶住」——取三者最短板 +1。任一方向缺一格，正方形就撑不起来。

合起来就是转移方程：

dp[i][j]=\begin{cases}\min\big(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1]\big)+1, & g[i][j]=1\\[4pt] 0, & g[i][j]=0\end{cases}

边界在首行、首列：上方或左方越界，正方形最多 $1\times1$ ，故 $g[i][j]=1$ 时 $dp[i][j]=1$ 。答案不在某个固定角落，而是全表最大的 $dp[i][j]$ （它的平方即最大面积）——因为正方形的右下角可能落在任何位置。

本质 · 短板决定边长

「以我为右下角的正方形」能有多大，取决于上、左、左上三个邻居里最弱的那个：只要有一个方向撑不到 $k$ ，我就凑不出 $k+1$ 的正方形。这个 $\min(\cdot)+1$ 把「逐格检查一个二维区域是否全 1」压成了 $O(nm)$ 一次扫描——二维状态最经典的一记：一格的答案，由它左上三邻的答案接力而来。

跟着算一遍

用引入图那张矩阵的左上一角走几步（行列都从 0 编号）。第 0 行原样落地 $1,0,1,1,0$ ，我们从第 1 行往里填：

0

首行落地。 第 0 行没有上方，能撑的正方形最多

1\times1

：格是 1 就记 1、是 0 就记 0 →

dp[0]=1,0,1,1,0

。首列同理。这是整张表的地基。

1

算 $dp[1][1]$ （本身

g=1

）。三来源：上

dp[0][1]=0

、左

dp[1][0]=1

、左上

dp[0][0]=1

，最短板是

0

，于是

dp[1][1]=0+1=1

——上方那个 0 把它死死压成了

1

。

2

算 $dp[1][3]$ （

g=1

）。三来源：上

dp[0][3]=1

、左

dp[1][2]=1

、左上

dp[0][2]=1

，最短板

1

，

dp[1][3]=1+1=2

——三邻都够到 1，于是这里长出一个

2\times2

正方形。

3

一路推到 $dp[3][3]$ 。此时它的上、左、左上分别是

2,2,2

，最短板

2

，

dp[3][3]=2+1=3

—— 全表最大值就是这个 3，对应那个

3\times3

全 1 块，面积

9

。

下面的演示会把整张

dp

表逐格填满，高亮每格的上 / 左 / 左上三来源并标出最短板。点矩阵里的格子可翻转 0↔1，看最大正方形实时重算。

看正方形一格一格长出来

0

1

2

3

4

0

1

2

3

·

当前计算依赖来源被选转移已确定

dp[i][j]=\min(dp[i-1][j],\ dp[i][j-1],\ dp[i-1][j-1])+1

为每一格计算以它为右下角的全 1 最大正方形边长；上、左、左上三处的短板决定能扩多大。

进度

已暂停，第 1 步，共 22 步，1 倍速

深化 · 双线程：两条路一起走

先说和 B 路径型的分工：双线程的四维朴素写法（ $dp[x_1][y_1][x_2][y_2]$ ）已在 B 路径型里随方格取数带出——那边侧重路径 DP 入门、顺手把四维摆出来；本页不再重复四维怎么来，而是专注把它压成三维 $dp[k][x_1][x_2]$ ，这正是「网格二维状态 + 压维」这一专章的重心。

网格 DP 的第二条主线，是同一张网格上有两条路径要一起规划——经典模型「传纸条」：两位同学分别从左上角出发、只能向右或向下，各自走到右下角，每格有一个好感度权值，问两条路径合计能收集的最大权值和（同一格被两条路都经过时，权值只算一次）。

为什么不能「先跑一条最优路，再跑第二条」？因为两条路会互相影响：第一条把高权值的格子占了，第二条就只能退而求其次——分开贪心必然错。正确做法是让两条路同时决策，状态一口气记住两条路各自的位置： $dp[x_1][y_1][x_2][y_2]$ ，四维，转移从两条路各自的「上 / 左」共 $4$ 种组合取 max（这正是 B 路径型里方格取数的四维写法）。

四维能压成三维。注意一个约束：两条路同步推进——走了同样多步的两条右/下路径，行号 + 列号必然相等，即 $x_1+y_1=x_2+y_2=k$ （都落在反对角线 $x+y=k$ 上）。既然列号能由 $y=k-x$ 反推，就不必单独存它，状态压成 $dp[k][x_1][x_2]$ ：

两条路径同步从左上走到右下：走了 k 步时，两条路都落在反对角线 x+y=k 上。只需记两条路当前的行号 x1、x2，列号 y=k−x 自动定出——四维 dp 压成三维 dp[k][x1][x2]。

转移：从 $k-1$ 层推到 $k$ 层，每条路上一步要么来自上方（ $x$ 减 1）、要么来自左方（ $x$ 不变、 $y$ 减 1），两条路组合出 $4$ 种来源取 max，再加上两条路当前所站两格的权值。关键一处：若两条路走到同一格（ $x_1=x_2$ ，此时 $y$ 也相等），那格权值只能加一次：

dp[k][x_1][x_2]=\max_{4\text{ prev}}dp[k-1]+a[x_1][y_1]+a[x_2][y_2]-[\,x_1=x_2\,]\cdot a[x_1][y_1]

把这套三维推进写成中文伪代码：

# 双线程 / 传纸条：两条路同步从 (0,0) 走到 (R-1,C-1)
dp[0][0] = a[0][0]                 # k=0，两条路都在起点，同格只算一次
for k = 1 … (R-1)+(C-1):          # 逐条反对角线
  for x1 in 合法行, x2 in 合法行:    # y1=k-x1, y2=k-x2（越界跳过）
    best = max over (路1 来自上/左) × (路2 来自上/左)   # 共 4 种
    add  = a[x1][y1] + a[x2][y2]
    if x1 == x2: add -= a[x1][y1]  # ★两路撞同格，权值只算一次
    dp[k][x1][x2] = best + add
answer = dp[最后一层][R-1][R-1]     # 两条路都到右下角

双线程要诀 · 同步推进 + 同格去重

「两条路径联合决策」的通法：让两条路同步走（步数相同），把两条路的位置拼进同一个状态一起转移，绝不各自贪心。由「同步」得到 $x_1+y_1=x_2+y_2=k$ ，可省掉一维压成 $dp[k][x_1][x_2]$ ；而两路可能重合，凡 $x_1=x_2$ 的格子记得扣掉一次重复权值。这两条一立，从「两条路」到「多条路」都是同一副骨架。

下面的演示把

dp[k][x_1][x_2]

摆成一张行 = 路1 行号、列 = 路2 行号的表，逐层 $k$ 填格；对角线上（

x_1=x_2

）的格子正是「两路撞在一起、权值去重」的地方。改网格权值或大小，看最大权值和实时重算。

看两条路同步推进

x2=0

x2=1

x2=2

x1=0

x1=1

x1=2

·

当前计算依赖来源被选转移已确定

dp[k][x_1][x_2]=\max_{4\text{ prev}}dp[k-1]+a[x_1][y_1]+a[x_2][y_2]

准备：两条路同步从左上出发，同一步数时都在反对角线 x+y=k 上；表格记录两条路当前行号组成的状态。

进度

已暂停，第 1 步，共 21 步，1 倍速

例题

P1387最大正方形洛谷原生普及/提高-

题意

给定

n\times m

的 0/1 矩阵，求只含 1 的最大正方形的边长（边长平方即面积）。

对应关系

本节主问题的裸模板。状态

f[i][j]

= 以

(i,j)

为右下角的最大全 1 正方形边长，答案取全表最大

f

。

转移 · 复杂度

f[i][j]=\min(f[i-1][j],\ f[i][j-1],\ f[i-1][j-1])+1

（

g[i][j]=1

时），否则

0

；一次扫描

O(nm)

。

参考代码（三格取 min）

C++

在洛谷打开 P1387

#include <iostream>
#include <algorithm>
using namespace std;

int n, m;
int g[105][105];                 // 原始 0/1 矩阵
int f[105][105];                 // f[i][j]：以 (i,j) 为右下角的最大全 1 正方形边长

int main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
            cin >> g[i][j];

    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (g[i][j] == 1)                       // 0 格当不了右下角，f 保持 0
                f[i][j] = min(min(f[i - 1][j], f[i][j - 1]), f[i - 1][j - 1]) + 1; // ★上/左/左上取 min
            ans = max(ans, f[i][j]);                // 全表最大边长
        }

    cout << ans << endl;                            // 题目要边长；面积则输出 ans*ans
    return 0;
}
// TAG: 矩阵DP 最大正方形 二维状态

P1006[NOIP2008 提高组] 传纸条NOIP2008 提高组普及+/提高

题意

m\times n

网格每格有一个好感度，两张纸条各从左上角走到右下角（只走右 / 下），两条路径不重叠，求两条路径好感度之和的最大值。

状态设计（双线程 / 按步压维）

让两条路同步推进：走了

k

步都落在反对角线

x+y=k

上，状态压成

f[k][x_1][x_2]

（列号

y=k-x

反推）。转移从两条路各自的「上 / 左」共

4

种组合取 max；两路撞在同格（

x_1=x_2

）时权值只算一次——这道自然逼你把「重叠去重」写进转移。

为什么选它

双线程 DP 的标杆题：真正的门槛不是转移，而是想到「两条路必须同时决策、位置一起进状态」，以及用「同步推进」把四维压成三维。学会它，方格取数、后续多路径问题都是同一副骨架。

参考代码（按步压维 dp[k][x1][x2]）

C++

在洛谷打开 P1006

#include <iostream>
#include <algorithm>
using namespace std;

int m, n;                        // m 行 n 列
int a[55][55];
// 按步数压维：dp[k][x1][x2]，列号 y = k - x 自动定出。两条路同步从 (1,1) 走到 (m,n)。
int f[105][55][55];

int main()
{
    cin >> m >> n;
    for (int i = 1; i <= m; i++)
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];

    int steps = m + n;           // 从 (1,1) 到 (m,n) 共走 (m-1)+(n-1) 步，k 从 2 到 m+n
    // 初始：k=2 时两条路都在 (1,1)，同格只算一次
    f[2][1][1] = a[1][1];

    for (int k = 3; k <= steps; k++)                 // 逐条反对角线推进
        for (int x1 = 1; x1 <= m; x1++)
        {
            int y1 = k - x1;
            if (y1 < 1 || y1 > n) continue;
            for (int x2 = 1; x2 <= m; x2++)
            {
                int y2 = k - x2;
                if (y2 < 1 || y2 > n) continue;
                // 上一步：每条路来自「上方 x-1」或「左方 x 不变」，四种组合取 max
                int best = max(max(f[k - 1][x1 - 1][x2 - 1], f[k - 1][x1 - 1][x2]),
                               max(f[k - 1][x1][x2 - 1], f[k - 1][x1][x2]));
                int add = a[x1][y1] + a[x2][y2];
                if (x1 == x2) add -= a[x1][y1];      // ★两路同格，权值只算一次
                f[k][x1][x2] = best + add;
            }
        }

    cout << f[steps][m][m] << endl;                  // 两路都到 (m,n)：x1=x2=m
    return 0;
}
// TAG: 矩阵DP 双线程 传纸条 按步压维

P1719最大加权矩形洛谷原生普及+/提高

题意

给定

n\times n

的整数权值矩阵（权值可正可负），求一个子矩形，使其中所有元素之和最大，输出这个最大和。

对应关系（二维子矩阵，非路径计数）

这是网格 DP 的另一副招牌形态：不再是「走路径」，而是「圈一块二维区域求最优」。做法是把一维最大子段和（Kadane）升到二维——枚举子矩形的上、下两行边界，把这两行之间每一列的和压成一个一维数组，对它跑一次最大子段和，即得跨这段行的最优子矩形。

转移 · 复杂度

列前缀和

s[i][j]

把「取

top..bot

行、第

j

列的和」压成

s[bot][j]-s[top-1][j]

；对该一维数组 Kadane：

cur=\max(col,\ cur+col)

。枚举

O(n^2)

对行边界，每次

O(n)

扫列，合计

O(n^3)

。

为什么选它

补齐 D 的二维区域视角（与「最大正方形」的二维状态递推互补），并把「一维经典算法升到二维」这个网格 DP 的常用手法讲透——与 B 路径型完全无重叠：那边是网格上「走路径」，这边是网格上「圈矩形」。

参考代码（列前缀和 + Kadane 升维）

C++

在洛谷打开 P1719

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;

int n;
int s[130][130];                 // s[i][j]：前 i 行、第 j 列的列前缀和（按行累积）

int main()
{
    cin >> n;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
        {
            int x;
            cin >> x;
            s[i][j] = s[i - 1][j] + x;              // ★只压「列方向」的前缀和
        }

    int ans = -0x3f3f3f3f;
    for (int top = 1; top <= n; top++)              // 枚举子矩形的上边界行
        for (int bot = top; bot <= n; bot++)        // 枚举下边界行
        {
            // 把 top..bot 这几行压成一维：第 j 列的和 = s[bot][j] - s[top-1][j]
            // 对这个一维数组跑一次最大子段和（Kadane），即得跨这段行的最优子矩形
            int cur = 0;
            for (int j = 1; j <= n; j++)
            {
                int col = s[bot][j] - s[top - 1][j];
                cur = max(col, cur + col);          // Kadane：要么另起，要么接上一段
                ans = max(ans, cur);
            }
        }

    cout << ans << endl;
    return 0;
}
// TAG: 矩阵DP 二维子矩阵 前缀和 最大子段和升维

练习

P1736创意吃鱼法最大正方形的变体（对角线版）：在 01 矩阵里找一个正方形，其某条对角线全是 1、其余格全是 0，求最长对角线。设 f[i][j] 为以 (i,j) 为右下角的合法正方形边长，转移 f[i][j]=min(f[i-1][j-1], 左侧连续 0 长, 上方连续 0 长)+1；两条对角线方向各扫一遍。仍是「左/上/左上邻格接力」的二维状态，与最大正方形同族。在洛谷打开

P2701[USACO5.3] 巨大的牛棚 Big Barn最大正方形的裸应用：N×N 农场里有若干棵树，求不含任何树的最大正方形边长。把「有树」当 0、「空地」当 1，转移就是 f[i][j]=min(f[i-1][j], f[i][j-1], f[i-1][j-1])+1，答案取全表最大——与本页 P1387 同一副模具，换了层皮。在洛谷打开

说明：纯二维网格状态（非路径计数）的洛谷原生题池并不宽——「网格上数路径」那一类已归到 B 路径型，此处只收本页招牌的「二维状态形态」题。上面两道都是最大正方形的直系变体；若想再练二维区域那一路，例题 P1719 最大加权矩形 可不看参考代码回炉默写（枚举行边界 + 每列压一维跑 Kadane）。

网格 / 矩阵上的 DP

本课摘要