1. 从一道经典题说起：最大正方形到底在考什么
第一次接触“最大正方形”这个题目，是在一个算法练习社区里。题干很朴素：给定一个由0和1组成的二维矩阵，找出其中只包含1的最大正方形，返回它的面积。看起来简单，但真正动手写的时候，很多人才发现里面藏着动态规划最精髓的那层思维——如何把一个大问题，拆成可以复用的小问题。
这个题目之所以经典，是因为它同时踩中了三个关键点：二维网格遍历、动态规划状态定义、以及边界条件的处理。它不像“爬楼梯”那样一眼就能看出递推关系，也不像“背包问题”那样有固定的模板可以套。你需要真正理解“为什么这个正方形能成立”，才能写出正确的状态转移方程。
我见过不少朋友在这道题上卡住，不是因为不会写代码，而是因为没想清楚一件事：一个以(i, j)为右下角的最大正方形，它的边长到底由什么决定？这个问题想通了，代码其实只有几行。想不通，就会陷入各种边界判断的泥潭。
这篇文章我会从零开始，把这道题的思路拆解、代码实现、优化技巧、常见坑点全部讲清楚。不管你是刚学动态规划的新手，还是想复习一下二维DP的老手，应该都能从中拿到一些实用的东西。尤其是那些“看题解能懂、自己写就错”的朋友，我会重点讲清楚状态转移背后的直觉，而不是只丢一个公式给你。
2. 核心思路拆解：为什么是动态规划
2.1 暴力解法的瓶颈在哪里
最直接的想法是：枚举每一个可能的正方形，检查它是否全由1组成。具体做法是，对于矩阵中每个位置(i, j)，尝试以它为左上角，枚举所有可能的边长k，然后检查这个k × k的区域是否全是1。
这个思路没错，但复杂度很吓人。假设矩阵是m × n，枚举左上角是O(mn)，枚举边长是O(min(m,n))，每次检查区域又是O(k²)，总复杂度大概在O(mn · min(m,n)³)这个量级。哪怕矩阵只有100 × 100，运算量也已经大到不可接受了。
更关键的是，暴力解法做了大量重复检查。比如你已经知道(i, j)到(i+2, j+2)这个3 × 3区域全是1，那么在检查4 × 4的时候，其实只需要看新增的那一行和一列。但暴力写法不会利用这个信息，每次都从头扫一遍。
这里其实就引出了动态规划的核心动机：把已经算过的结果存下来，避免重复计算。
2.2 动态规划的状态定义
动态规划的第一步，永远是定义状态。对于这道题，一个非常自然的定义是：
dp[i][j]表示以(i, j)为右下角的最大正方形的边长。
注意关键词是“右下角”，不是左上角。这个选择很关键，后面会解释为什么。
有了这个定义之后，我们要求的就是所有dp[i][j]中的最大值，然后返回它的平方（因为题目要的是面积）。
那dp[i][j]怎么算呢？如果matrix[i][j] == '0'，那显然dp[i][j] = 0，因为以它为右下角根本不可能构成正方形。
如果matrix[i][j] == '1'，那它至少可以自己构成一个1 × 1的正方形，所以dp[i][j]至少是1。但能不能更大，取决于它左边、上边、左上角这三个位置的状态。
2.3 状态转移方程的直觉推导
这是整道题最核心的部分。很多人背下了公式dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1，但问他为什么，答不上来。我来用一个具体的例子把这个直觉讲透。
假设我们现在站在(i, j)位置，这个格子是1。我们想知道以它为右下角的最大正方形边长是多少。
想象一下，如果以(i, j)为右下角能构成一个边长为k的正方形，那么这个正方形的：
- 左边一列，必须以
(i, j-1)为右下角构成一个边长为k-1的正方形； - 上边一行，必须以
(i-1, j)为右下角构成一个边长为k-1的正方形； - 左上角那个
(k-1) × (k-1)的区域，必须以(i-1, j-1)为右下角构成一个边长为k-1的正方形。
这三个条件是“同时满足”的。换句话说，dp[i][j]能取到k，当且仅当这三个方向的dp值都至少是k-1。
所以dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。取最小值，是因为三个条件必须同时满足，短板决定上限。加一，是因为当前格子本身贡献了1的边长。
这个“短板效应”是理解这道题的关键。你可以把它想象成：三个人一起抬一个箱子，箱子能抬多高，取决于最矮的那个人。
2.4 为什么用右下角而不是左上角
这个问题值得单独说一下。用右下角作为状态的定义锚点，最大的好处是递推方向自然。我们遍历矩阵的时候，通常是从左上到右下，那么(i-1, j)、(i, j-1)、(i-1, j-1)这三个位置在遍历到(i, j)的时候都已经算过了，可以直接用。
如果用左上角定义dp[i][j]表示以(i, j)为左上角的最大正方形边长，那递推就要依赖(i+1, j)、(i, j+1)、(i+1, j+1)，遍历方向就得反过来。虽然也能做，但代码写起来别扭，边界处理也更麻烦。
所以这不是什么高深的技巧，就是一个“顺着遍历方向定义状态”的工程习惯。很多二维DP题目都有这个特点：状态定义的方向要和遍历方向一致，这样代码最简洁。
3. 代码实现与逐行解析
3.1 基础版本：二维DP数组
先把最直观的版本写出来，用完整的二维数组存状态。
def maximalSquare(matrix): if not matrix or not matrix[0]: return 0 m, n = len(matrix), len(matrix[0]) dp = [[0] * n for _ in range(m)] max_side = 0 for i in range(m): for j in range(n): if matrix[i][j] == '1': if i == 0 or j == 0: dp[i][j] = 1 else: dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1 max_side = max(max_side, dp[i][j]) return max_side * max_side这段代码有几个细节值得说：
第一，边界处理。当i == 0或j == 0时，也就是第一行或第一列，不可能构成比1 × 1更大的正方形，所以直接赋值为1。这个判断不能省，否则访问dp[i-1]会越界。
第二，max_side的更新放在if里面。因为只有当前格子是1的时候，dp[i][j]才有意义。如果放在外面，遇到0的格子会把max_side错误地更新为0。
第三，返回值是max_side * max_side，因为题目要的是面积，不是边长。这个很容易看错，我见过有人返回边长然后纳闷为什么答案不对。
3.2 空间优化版本：一维数组滚动
二维数组的空间复杂度是O(mn)。如果矩阵很大，这个空间开销是不能忽略的。但其实我们注意到，计算dp[i][j]只依赖上一行的dp[i-1][j]、dp[i-1][j-1]和当前行左边的dp[i][j-1]。也就是说，我们只需要保留“上一行”和“当前行”的信息就够了。
进一步优化，可以用一个一维数组，在遍历过程中不断更新。但这里有个坑：dp[i-1][j-1]在更新dp[j]的时候会被覆盖掉，所以需要用一个变量提前存起来。
def maximalSquare(matrix): if not matrix or not matrix[0]: return 0 m, n = len(matrix), len(matrix[0]) dp = [0] * (n + 1) max_side = 0 prev = 0 # 用来保存 dp[i-1][j-1] for i in range(1, m + 1): for j in range(1, n + 1): temp = dp[j] # 保存当前 dp[j]，它将成为下一轮的 prev if matrix[i-1][j-1] == '1': dp[j] = min(dp[j], dp[j-1], prev) + 1 max_side = max(max_side, dp[j]) else: dp[j] = 0 prev = temp return max_side * max_side这个版本的技巧在于prev变量。在更新dp[j]之前，先把旧的dp[j]（也就是上一行的dp[i-1][j]）存到temp里。等这一轮处理完，temp就变成了下一轮的prev，也就是dp[i-1][j-1]。
这个“用变量暂存被覆盖的值”是滚动数组优化的通用套路，在很多DP题目里都能用到。第一次写容易绕晕，建议拿纸笔画一下
i和j的变化过程。
空间复杂度从O(mn)降到了O(n)。如果n比m大，可以转置一下矩阵，让n取较小的那个维度，进一步省空间。
3.3 两种写法的对比
| 维度 | 二维DP | 一维滚动DP |
|---|---|---|
| 时间复杂度 | O(mn) | O(mn) |
| 空间复杂度 | O(mn) | O(n) |
| 代码可读性 | 高，直观 | 中，需要理解prev的作用 |
| 边界处理 | 需要单独判断第一行第一列 | 通过dp数组多开一位统一处理 |
| 适用场景 | 面试手写、教学 | 工程实现、空间敏感场景 |
面试的时候我一般建议先写二维版本，因为逻辑清晰、不容易出错。如果面试官追问空间优化，再写一维版本。工程里如果矩阵规模不大，二维版本也完全够用，没必要为了省一点空间把代码搞得难懂。
4. 实操中的坑点与排查技巧
4.1 字符与数字的混淆
这是最高频的错误。题目给的矩阵通常是字符'0'和'1'，不是数字0和1。如果你写if matrix[i][j] == 1，在Python里永远为False，因为'1' != 1。结果就是max_side一直是0，返回0。
排查方法很简单：打印一下matrix[0][0]的类型，看看是str还是int。如果是字符串，比较的时候必须加引号。
4.2 边界条件漏判
二维版本里，如果忘了判断i == 0 or j == 0，访问dp[i-1][j]时会越界。Python会报IndexError，但如果是用其他语言，可能会读到脏数据，导致结果莫名其妙。
一个更优雅的处理方式是给dp数组多开一行一列，全部初始化为0，这样就不用单独判断边界了。代码会变成这样：
dp = [[0] * (n + 1) for _ in range(m + 1)] 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 max_side = max(max_side, dp[i][j])这种“哨兵边界”的写法在二维DP里非常常见，能省掉一堆if-else，代码更干净。
4.3 返回值的单位搞错
题目要的是面积，不是边长。max_side存的是边长，返回的时候要平方。我见过有人返回max_side，然后测试用例[["1"]]期望输出1，恰好蒙对了，但换成[["1","1"],["1","1"]]期望输出4，返回2就错了。
4.4 常见问题速查表
| 现象 | 可能原因 | 解决方法 |
|---|---|---|
| 返回结果始终为0 | 字符与数字比较错误 | 检查matrix[i][j] == '1'是否加了引号 |
| 报数组越界 | 边界条件未处理 | 加i==0 or j==0判断，或dp数组多开一行一列 |
| 结果比预期小 | 返回值忘记平方 | 返回max_side * max_side |
| 一维版本结果错乱 | prev变量更新顺序错误 | 确保先存temp，再更新dp[j]，最后更新prev |
| 矩阵为空时报错 | 未处理空输入 | 开头加if not matrix or not matrix[0]: return 0 |
4.5 一个容易被忽略的优化点
如果矩阵中1的密度很低，其实可以先做一次快速判断：如果当前max_side已经大于等于剩余可能的最大边长，就可以提前终止。不过这个优化在实际面试中很少需要，因为DP本身已经是O(mn)了，再优化意义不大。但在某些特定场景下，比如矩阵超大但1很稀疏，这个剪枝能省不少时间。
5. 从这道题延伸出去：还能怎么玩
5.1 最大矩形：从正方形到矩形
“最大正方形”有一个著名的变体叫“最大矩形”，题目是：在同样的0/1矩阵中，找出只包含1的最大矩形面积。这道题的难度比最大正方形高不少，因为它不再要求长宽相等，状态定义和转移方程都要重新设计。
最大矩形的经典解法是“柱状图最大矩形”的扩展：把每一行看作一个柱状图的底部，统计每个位置向上连续1的高度，然后对每一行调用一次“柱状图中最大矩形”的算法。这个思路非常巧妙，值得单独写一篇文章来讲。
5.2 统计全为1的正方形子矩阵
另一个变体是：统计矩阵中全为1的正方形子矩阵的个数。这道题和最大正方形几乎是同一套DP，只不过最后不是取max，而是把所有dp[i][j]加起来。因为dp[i][j]表示以(i, j)为右下角的正方形边长，那么以它为右下角的正方形个数恰好就是dp[i][j]个（边长分别为1, 2, ..., dp[i][j]）。
这个性质很漂亮，也说明最大正方形的DP状态定义具有很强的扩展性。
5.3 实际应用场景
这类“在网格中找最大全1区域”的问题，在实际工程中是有对应场景的。比如：
- 图像处理：在二值图像中找最大的连通矩形区域，用于目标检测或区域裁剪。
- 芯片布局：在芯片版图上找最大的可用正方形区域，用于放置特定模块。
- 游戏开发：在瓦片地图中找最大的可建造区域，用于AI自动建造。
- 数据分析：在用户行为矩阵中找最大的密集交互区块，用于推荐或异常检测。
虽然实际场景中矩阵规模可能远大于算法题，但核心思路是一样的。工程上可能会加上分块处理、并行计算等优化，但DP的那层逻辑不会变。
6. 我个人在刷这道题时的几点体会
第一次做这道题的时候，我是直接看题解的。看完觉得“哦，原来这么简单”，然后关掉题解自己写，结果卡在边界条件上改了半小时。后来我总结出一个习惯：每道DP题，先自己在纸上画一个3×3或4×4的小矩阵，手动填一遍dp表，再写代码。这个习惯帮我省了很多调试时间。
另外，关于状态转移方程的min操作，我一开始总是记成max，觉得“要取最大的正方形嘛，当然取max”。后来想明白了：dp[i][j]能不能变大，取决于三个方向是不是都够大，所以是取最小值。这个直觉一旦建立起来，就再也不会记错了。
还有一点，一维滚动数组的写法，我建议至少在纸上推导一遍prev的变化过程。不要觉得“看懂了”就跳过，真正写的时候那个覆盖顺序很容易搞反。我自己是画了一个3 × 3的表格，标出每一步dp[j]和prev的值，才彻底搞清楚。
最后分享一个小技巧：如果你在面试中遇到这道题，可以先说暴力解法，然后说“这里有很多重复计算，可以用DP优化”，再给出状态定义和转移方程。这样展示的是一个完整的思考过程，比直接背出最优解更能打动面试官。而且万一转移方程一时想不起来，前面的分析也能帮你争取时间。
这道题后续还可以这样扩展：试着把矩阵改成三维，找最大的全1立方体。状态定义会变成dp[i][j][k]，转移方程要考虑七个方向的最小值。思路是一样的，但维度上去之后，空间优化会变得更有挑战性。有兴趣的朋友可以自己试试。
