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)到(i2, j2)这个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)为左上角的最大正方形边长那递推就要依赖(i1, j)、(i, j1)、(i1, j1)遍历方向就得反过来。虽然也能做但代码写起来别扭边界处理也更麻烦。所以这不是什么高深的技巧就是一个“顺着遍历方向定义状态”的工程习惯。很多二维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是否加了引号报数组越界边界条件未处理加i0 or j0判断或dp数组多开一行一列结果比预期小返回值忘记平方返回max_side * max_side一维版本结果错乱prev变量更新顺序错误确保先存temp再更新dp[j]最后更新prev矩阵为空时报错未处理空输入开头加if not matrix or not matrix[0]: return 04.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]转移方程要考虑七个方向的最小值。思路是一样的但维度上去之后空间优化会变得更有挑战性。有兴趣的朋友可以自己试试。