题目描述
思路解析
一句话答案：LeetCode 221 最大正方形的标准解法是二维动态规划：dp[i][j] 定义为「以 (i,j) 为右下角的全 1 正方形的最大边长」，转移取上、左、左上三个邻居的最小值再加 1——正方形能扩多大由最短的方向决定。扫一遍矩阵记录最大边长 k，答案是面积 k²，时间 O(m·n)。
最大正方形这道题在问什么
给一个只含 0 和 1 的矩阵，找出其中面积最大、内部全是 1 的正方形，返回它的面积。两个容易看漏的点：一是要的是正方形不是矩形，长宽必须相等；二是题目问的是面积，算出最大边长后别忘了平方再返回。
为什么暴力枚举正方形太慢
直觉做法是枚举每个格子当正方形的一个角，再枚举每种边长，逐格检查内部是否全 1。m×n 的矩阵有 m·n 个起点、每个起点最多 min(m,n) 种边长、每次检查又要看边长平方个格子，几层循环叠上去开销很大，而且大量检查在重复劳动——边长 3 的正方形内部那些格子，早在检查边长 2 时就看过一遍了。
重复劳动提示了突破口：一个大正方形成不成立，其实不必逐格重查，它可以由「旁边更小的正方形成不成立」直接推出来。能用小结论拼大结论，就是动态规划的信号。
dp 为什么定义成「以这格为右下角的最大边长」
定义 dp[i][j] 为：以格子 (i,j) 作为右下角、内部全 1 的正方形的最大边长。选「右下角」做锚点是因为每个正方形都有且只有一个右下角——按右下角分类枚举，所有正方形不重不漏；而值存边长而非面积，是为了让相邻格子的结论能直接做算术比较。原图为 0 的格子当不了任何全 1 正方形的右下角，dp 直接记 0。
整张 dp 表填完后，全局最大的 dp 值就是最大边长，平方即答案。
为什么取上左左上三者的最小值加一
想以 (i,j) 为右下角撑起一个边长 k 的正方形，等价于三件事同时成立：它上边那格能撑住边长 k-1 的正方形（覆盖上方区域）、左边那格能撑住 k-1（覆盖左侧区域）、左上那格也能撑住 k-1（覆盖左上对角区域），三块拼起来恰好铺满除当前格外的整个 k×k 区域。三个方向里任何一个短了，大正方形就在那个方向缺角，所以能扩到的边长由短板决定——取三者最小值，再加 1 把当前这格接进来，就是转移方程 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。
只看上、左两个邻居为什么不行？因为它们都撑得住时，左上方向可能有空洞——上邻居和左邻居的正方形呈 L 形交叠，中间左上那块没人担保。左上邻居正是补上这块担保的，少一个都会把有洞的区域误判成实心正方形。
复杂度怎么算，实现上有哪些细节
每个格子只算一次、每次 O(1)，时间 O(m·n)；dp 表空间 O(m·n)。由于每格只依赖上一行和本行左边，可以用一维数组加一个变量缓存「左上」旧值，把空间压到 O(n)。
实现细节有三个：给 dp 表多加一圈全 0 的哨兵行列，首行首列就不用单独判边界；矩阵元素通常是字符 '1' 而不是数字 1，比较时别写错；最后返回 best × best 而不是 best。对照示例，那个 4×5 矩阵里最大边长是 3，答案是 9。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
关键直觉：一个大正方形要成立，它右下角左边、上边、左上三个方向都得各自撑住一个略小的正方形——短板决定了能扩多大。
最上面一行、最左边一列是「哨兵」，全填 0（表示越界处没有正方形）。这样每个真实格子都一定有上/左/左上三个邻居可看，不用判边界。
格 (1,1) 原图是 1：看它的上=0、左=0、左上=0，取最小的当短板，再 +1。
三邻居最小是 0，+1 得 1：以 (1,1) 为右下角能凑出边长 1 的正方形。
格 (1,2) 原图是 0：这里不可能当正方形右下角，直接记 0。
填 0，继续往右走。
格 (1,3) 原图是 1：看它的上=0、左=0、左上=0，取最小的当短板，再 +1。
三邻居最小是 0，+1 得 1：以 (1,3) 为右下角能凑出边长 1 的正方形。
格 (1,4) 原图是 1：看它的上=0、左=1、左上=0，取最小的当短板，再 +1。
三邻居最小是 0，+1 得 1：以 (1,4) 为右下角能凑出边长 1 的正方形。
格 (1,5) 原图是 1：看它的上=0、左=1、左上=0，取最小的当短板，再 +1。
三邻居最小是 0，+1 得 1：以 (1,5) 为右下角能凑出边长 1 的正方形。
格 (2,1) 原图是 1：看它的上=1、左=0、左上=0，取最小的当短板，再 +1。
三邻居最小是 0，+1 得 1：以 (2,1) 为右下角能凑出边长 1 的正方形。
格 (2,2) 原图是 1：看它的上=0、左=1、左上=1，取最小的当短板，再 +1。
三邻居最小是 0，+1 得 1：以 (2,2) 为右下角能凑出边长 1 的正方形。
格 (2,3) 原图是 1：看它的上=1、左=1、左上=0，取最小的当短板，再 +1。
三邻居最小是 0，+1 得 1：以 (2,3) 为右下角能凑出边长 1 的正方形。
格 (2,4) 原图是 1：看它的上=1、左=1、左上=1，取最小的当短板，再 +1。
三邻居最小是 1，+1 得 2：以 (2,4) 为右下角能凑出边长 2 的正方形。
格 (2,5) 原图是 1：看它的上=1、左=2、左上=1，取最小的当短板，再 +1。
三邻居最小是 1，+1 得 2：以 (2,5) 为右下角能凑出边长 2 的正方形。
格 (3,1) 原图是 1：看它的上=1、左=0、左上=0，取最小的当短板，再 +1。
三邻居最小是 0，+1 得 1：以 (3,1) 为右下角能凑出边长 1 的正方形。
格 (3,2) 原图是 1：看它的上=1、左=1、左上=1，取最小的当短板，再 +1。
三邻居最小是 1，+1 得 2：以 (3,2) 为右下角能凑出边长 2 的正方形。
格 (3,3) 原图是 1：看它的上=1、左=2、左上=1，取最小的当短板，再 +1。
三邻居最小是 1，+1 得 2：以 (3,3) 为右下角能凑出边长 2 的正方形。
格 (3,4) 原图是 1：看它的上=2、左=2、左上=1，取最小的当短板，再 +1。
三邻居最小是 1，+1 得 2：以 (3,4) 为右下角能凑出边长 2 的正方形。
格 (3,5) 原图是 0：这里不可能当正方形右下角，直接记 0。
填 0，继续往右走。
格 (4,1) 原图是 0：这里不可能当正方形右下角，直接记 0。
填 0，继续往右走。
格 (4,2) 原图是 1：看它的上=2、左=0、左上=1，取最小的当短板，再 +1。
三邻居最小是 0，+1 得 1：以 (4,2) 为右下角能凑出边长 1 的正方形。
格 (4,3) 原图是 1：看它的上=2、左=1、左上=2，取最小的当短板，再 +1。
三邻居最小是 1，+1 得 2：以 (4,3) 为右下角能凑出边长 2 的正方形。
格 (4,4) 原图是 1：看它的上=2、左=2、左上=2，取最小的当短板，再 +1。
三邻居最小是 2，+1 得 3：以 (4,4) 为右下角能凑出边长 3 的正方形。
格 (4,5) 原图是 1：看它的上=0、左=3、左上=2，取最小的当短板，再 +1。
三邻居最小是 0，+1 得 1：以 (4,5) 为右下角能凑出边长 1 的正方形。
整张表里最大的 dp 是 3（在格 (4,4)），它就是最大正方形的边长。面积 = 3² = 9。
边界先想清。
两个高频追问。
参考代码
def maximalSquare(matrix): m, n = len(matrix), len(matrix[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复杂度
- 时间：O(m·n)，每格只算一次
- 空间：O(m·n)，dp 表（可滚动压到 O(n)）
易错点
面试追问把动画讲成自己的话
追问为什么是 min 而不是 max？
追问怎么把空间压到 O(n)？
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
完全平方数
LeetCode 279 · 中等 · 沿着 二维动态规划 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题