§1

题目描述

给一个只含 0 和 1 的矩阵，找出只由 1 组成的最大正方形，返回它的面积。

matrix = 4×4，右下角藏着一块 3×3 的 1

输出 = 9（边长 3，面积 3×3）

§2

思路解析动画文字版

最直接的想法：把每个格子都当正方形的右下角，再一圈一圈往外扩，每扩一层都要把那一整圈格子重新检查一遍是不是全 1。格子多、边长大时，同一片区域被反复扫，慢得离谱。痛点在于：相邻格子的检查结果被白白丢掉、每次都从头来。

换个记法：让 dp[i][j] 记住「以这个格子作右下角，能撑出的最大正方形边长」。这样每个格子只算一次、还能借用左、上、左上三个邻居已经算好的结果——这正是上面笨办法重复扫的那部分，现在全省下来。

如果当前格自己是 1，想让它当一个边长 3 正方形的右下角，那它正左边、正上边、左上角这三个格子，必须各自都能当一个边长 2 正方形的右下角——三块边长 2 的正方形加上当前格，刚好严丝合缝拼成边长 3。只要有一个邻居撑不到，就拼不齐。所以当前边长被三个邻居里最小的那个决定。

原矩阵 + 一张同样大的 dp 表：这是要处理的 4×4 矩阵（formula 那行列出每行的 0/1）。咱再开一张同样大小的 dp 表，先全空，等会儿从左上往右下一格一格填，每格填「以它为右下角的最大正方形边长」。

地基：第一行、第一列：最上面一行和最左边一列没有完整的左、上、左上三个邻居，撑不出更大的正方形。所以规则很简单：原格是 1 就填 1，是 0 就填 0。注意行0列2、行2列0这两个 0 原样填 0。

第一个内部格 (1,1)：看三个邻居：来到 (1,1)，原格是 1。看它的三个邻居：上=1、左=1、左上=1，三个都至少 1。取最小值 1 再 +1，所以这一格能撑边长 2。

(1,1) 填 2：第一块 2×2 出现：把 2 填进 (1,1)。这个 2 不是凭空来的：它说「以我为右下角，左、上、左上各借一格，正好围出一块 2×2 全 1 的正方形」。best 边长更新成 2。

填完行1、行2：继续一格格往右、往下填。提醒一处：行1列2上面原矩阵那块有个 0（行0列2=0），所以 (1,2) 的「上邻居」是 0，min 一拉就只有 1——一个 0 邻居会把正方形死死按在边长 1。表填到行2，已经看到 (2,2)=2，又一块 2×2。

⚠️ 短板时刻：(2,3) 为什么只有 2：这是全题最该停下看的一帧。(2,3) 自己是 1，左邻居已经是 2，看着像要长到 3 了——可上邻居只有 1、左上也只有 1。木桶装多少水看最短那块板：min(1,2,1)+1 只能是 2。一个邻居拖后腿，整块正方形就长不大。

🏆 climax：(3,3) 凑齐三个 2：填到右下角 (3,3)，原格是 1。这次三个邻居上=2、左=2、左上=2整整齐齐，三块 2×2 加自己，min(2,2,2)+1 = 3！这是第一次有格子撑到边长 3。

答案：边长 3，面积 9：整张表填完，里面最大的数字是 (3,3) 的 3，就是全矩阵能拼出的最大正方形边长。题目要面积，所以边长平方：3×3 = 9。注意返回的是 best 平方，不是 best 本身。

一句话记住这题：dp[i][j] = min(三个邻居) + 1。木桶能装多少水看最短的板，正方形能撑多大看最弱的邻居。

面试追问：这几问几乎必考：状态为什么选右下角、为什么是 min、能不能压空间、以及和最大长方形的区别。

迁移阶梯：记牢「以右下角为状态 + 取邻居最小 + 边界即地基」这套路，就能往上爬：最大长方形（85，转单调栈）、统计全 1 子矩形个数（1277，把 dp 值直接累加）。卡住时点开右侧小欧 AI 私教问一句「为什么这里用 min」，或去通关训练里找同款二维 DP 连刷几道。

边界三连：三个边界：空矩阵要先判空别越界；单格答案就是它自己；全 1 时正方形边长是 min(m,n)，验证 min+1 的转移在极端情况也成立。

§3

参考代码

class Solution:    def maximalSquare(self, matrix):        m, n = len(matrix), len(matrix[0])        # 多开一圈 0，省掉第一行/第一列的特判        dp = [[0]*(n+1) for _ in range(m+1)]        best = 0        for i in range(1, m+1):            for j in range(1, n+1):                if matrix[i-1][j-1] == '1':                    dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1                    best = max(best, dp[i][j])        return best * best

看懂代码不等于写得出。盖住上面，自己默写一遍试试。卡在哪一行说不清，就点右下角问小欧。

§4

复杂度

时间复杂度：O(m·n)，每个格子只填一次，填的时候查左/上/左上三个已算好的邻居，是 O(1)；总共 m×n 个格子
空间复杂度：O(m·n)，一张和矩阵同样大的 dp 表；因为只依赖上一行，可滚动压到 O(n)

§5

可套用的代码模板

这是挖空骨架不是答案：cell_ok / base / combine / best 四个空，本题分别填 matrix=='1'、填 1、min+1、max（最后面积再平方）。换到「统计全 1 子矩形」combine 就改成加法、best 改成累加——状态和填表顺序不动，只换这四个零件。

# 矩阵区域型二维 DP · 可背骨架# ① 状态：dp[i][j] = 以 (i,j) 为右下角的某个量（边长/计数/最优）# ② 边界：第一行、第一列就是地基（这里 = matrix 本身的值）# ③ 转移：当前格满足条件时，由 上/左/左上 三个邻居推出dp = [[0]*n for _ in range(m)]for i in range(m):    for j in range(n):        if cell_ok(i, j):                 # ← 本题：matrix[i][j] == '1'            if i == 0 or j == 0:                dp[i][j] = base(i, j)     # ← 本题：1            else:                dp[i][j] = combine(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])                # ← 本题 combine = min(...) + 1            ans = best(ans, dp[i][j])     # ← 本题：max；面积再平方

§6

易错点

✗ 错误写法：用 max(三邻居)+1

✓ 正确写法：必须用 min(三邻居)+1

max 会让一个长邻居就把正方形吹大，实际撑不齐——min 才保证三块都够长

✗ 错误写法：只看左、上两个邻居

✓ 正确写法：还要看左上角那个邻居

漏掉左上，L 形或缺角的区域会被误判成完整正方形

✗ 错误写法：返回 best（边长）

✓ 正确写法：返回 best * best（面积）

题目要的是面积，边长 3 的答案是 9 不是 3

✗ 错误写法：matrix 里是字符 '1' 却按数字 1 比

✓ 正确写法：比较 matrix[i][j] == '1'（带引号）

LeetCode 这题矩阵元素是字符 char，不是 int，写错恒不进分支、答案全 0

面试追问把动画讲成自己的话

追问dp 状态为什么定义成「以 (i,j) 为右下角」，而不是「左上角」或「包含 (i,j)」？

定成右下角，转移就只依赖左、上、左上这三个已经算过的格子，天然符合从左上往右下的填表顺序；定成左上角则要依赖右、下方还没算的格子，反着来很别扭。

追问为什么是 min 不是 max？能用一句话证明吗？

想以 (i,j) 为右下角撑出边长 k，必须左、上、左上同时都能撑 k−1，三块边长 k−1 的正方形才拼得满。只要有一块不够，就只能取到那块的尺寸——所以是三者取最小再加 1。

追问能优化到 O(n) 空间吗？

能。dp[i][j] 只用到当前行的左邻居、上一行的同列和上一行的左邻居，保留一行即可。用一维数组滚动，再拿一个变量缓存「左上角」那个会被覆盖掉的旧值，空间降到 O(n)。

追问如果问的是最大长方形面积（LeetCode 85）而不是正方形，这套还管用吗？

不直接管用。长方形宽高可以不等，这个 min+1 的对称结构就失效了。85 题的主流解法是把每一行压成柱状图，再用单调栈求「柱状图中最大矩形」。

这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：

下一题 · 二维动态规划 13/15

完全平方数

LeetCode 279 · 中等 · 沿着二维动态规划继续往下推进

→

把这道题真正学会，再走

图解算法年卡 ¥99 /年

✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
✓学习报告，记录每道题的掌握程度

299道动画图解

37节语音讲解

28课数据结构

¥0.27折合 / 天

76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解

¥99 开通年卡 →

想成体系刷透这类套路？去图解算法专题

class Solution: def maximalSquare(self, matrix): m, n = len(matrix), len(matrix[0]) # 多开一圈 0，省掉第一行/第一列的特判 dp = [[0]*(n+1) for _ in range(m+1)] best = 0 for i in range(1, m+1): for j in range(1, n+1): if matrix[i-1][j-1] == '1': dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 best = max(best, dp[i][j]) return best * best

# 矩阵区域型二维 DP · 可背骨架# ① 状态：dp[i][j] = 以 (i,j) 为右下角的某个量（边长/计数/最优）# ② 边界：第一行、第一列就是地基（这里 = matrix 本身的值）# ③ 转移：当前格满足条件时，由上/左/左上三个邻居推出dp = [[0]*n for _ in range(m)]for i in range(m): for j in range(n): if cell_ok(i, j): # ← 本题：matrix[i][j] == '1' if i == 0 or j == 0: dp[i][j] = base(i, j) # ← 本题：1 else: dp[i][j] = combine(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) # ← 本题 combine = min(...) + 1 ans = best(ans, dp[i][j]) # ← 本题：max；面积再平方