1. 从一道题看动态规划的降维打击最大正方形这四个字第一次看到的人多半会以为是个几何题甚至有人会下意识去翻勾股定理。但只要你刷过几道算法题就会明白这类问题真正的战场不在几何而在动态规划。它是一道非常经典的二维网格DP入门题也是很多人从暴力枚举思维切换到状态转移思维的分水岭。我拿这道题做过一个小范围的统计身边十个刚接触算法的朋友里有八个第一反应是枚举所有正方形检查是不是全1。这个思路没错但复杂度直接飙到O(n³·m)甚至更高网格稍微大一点就超时。而正确的解法时间复杂度只有O(n·m)空间复杂度还能从O(n·m)压到O(m)。这中间的差距就是动态规划带来的降维打击。这篇文章我会把最大正方形这道题彻底拆开讲透。不管你是刚学DP的新手还是想复习二维DP状态设计的老手都能从中拿到东西。我会从暴力解法的瓶颈讲起一步步推导状态定义、转移方程、边界处理再延伸到空间优化、变体题型和实际工程中的类似场景。所有代码都会给出完整可运行的版本参数和推导过程都会写清楚方便你直接抄作业。提示本文默认读者了解基本的数组操作和循环嵌套不要求提前掌握动态规划。如果你连状态这个词都没听过也没关系我会用生活化的例子把它讲明白。2. 暴力枚举为什么在真实网格上跑不动2.1 最直觉的解法以每个点为左上角去试拿到一个由0和1组成的二维矩阵要求找出只包含1的最大正方形面积。最朴素的想法是这样的遍历每一个格子把它当作正方形的左上角然后尝试边长从1开始递增每次检查这个正方形区域内是不是全是1记录下最大的边长最后返回边长的平方。这个思路的代码写起来大概是这样def maximal_square_brute(matrix): if not matrix or not matrix[0]: return 0 rows, cols len(matrix), len(matrix[0]) max_side 0 for i in range(rows): for j in range(cols): if matrix[i][j] 1: # 尝试以(i,j)为左上角边长从1开始 side 1 while i side rows and j side cols: # 检查新增的一行和一列是否全为1 ok True for k in range(side): if matrix[i side - 1][j k] ! 1 or matrix[i k][j side - 1] ! 1: ok False break if not ok: break side 1 max_side max(max_side, side - 1) return max_side * max_side这段代码的逻辑是每次边长增加1只需要检查新扩展的那一行和一列而不是把整个正方形重新扫一遍。这已经是一个小优化了但整体复杂度依然很高。2.2 复杂度到底高在哪里我们来算一笔账。假设网格是n×n的最坏情况下全是1。对于每个左上角(i,j)边长最多能扩展到min(n-i, n-j)。每次扩展检查O(side)个格子。把所有左上角加起来总的操作次数大约是对于边长为s的正方形有(n-s1)²个位置每个位置扩展检查的代价是O(s)求和得到Σ(s1到n) (n-s1)² · s这个量级是O(n⁴)。即使有只检查新增行列的优化也只是把常数降下来量级依然是O(n³)左右。当n1000时n³就是10亿次操作在大多数在线评测环境里直接超时。更关键的是暴力解法做了大量重复计算。比如判断以(0,0)为左上角、边长为3的正方形是否全1时其实已经隐含了以(0,0)为左上角、边长为2的正方形全1这个信息。但暴力解法不会复用这个信息每次都从头检查。这就是动态规划要解决的核心问题把重复的子问题结果存下来避免重复计算。2.3 一个生活化的类比你可以把这个问题想象成盖楼。暴力解法是每盖一层楼都从地基开始重新检查一遍砖块有没有问题。而动态规划的思路是我知道下面那层楼是合格的那我盖新一层时只需要检查新加的砖块以及和邻居的衔接处就行了。这个衔接处的检查正是最大正方形DP转移方程的精髓所在。下面我们就来正式推导。3. 状态定义与转移方程的完整推导3.1 状态怎么定义才不重不漏动态规划的第一步永远是定义状态。对于二维网格问题最自然的想法是dp[i][j]表示什么这里有一个常见的误区。很多人会想定义dp[i][j]为以(i,j)为左上角的最大正方形边长。这个定义不是不行但转移起来很别扭因为正方形的扩展方向是向右下而遍历顺序通常是从左上到右下两者方向一致但依赖关系不好处理。更优雅的定义是dp[i][j]表示以(i,j)为右下角、且只包含1的最大正方形边长。注意关键词右下角。这个定义的好处是当我们从左到右、从上到下遍历时计算dp[i][j]所需要的所有子问题dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]都已经计算过了。为什么选右下角而不是左上角因为DP的遍历顺序通常是从小下标到大下标以右下角为锚点子问题的下标都更小天然满足无后效性。如果你选左上角子问题下标更大就得倒着遍历虽然也能做但不符合大多数人的思维习惯。3.2 转移方程的几何直觉现在关键问题来了已知dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]怎么推出dp[i][j]先看一个具体的例子。假设矩阵是1 1 1 1 1 1 1 1 1我们来看dp[2][2]右下角那个格子。它的左边dp[2][1]2上边dp[1][2]2左上dp[1][1]2。三个都是2所以dp[2][2]3。再看一个例子1 1 1 1 0 1 1 1 1中间是0。对于dp[2][2]左边dp[2][1]以(2,1)为右下角的最大正方形由于(2,0)(2,1)都是1(1,1)是0所以dp[2][1]1。上边dp[1][2]同理等于1。左上dp[1][1]1。三个都是1所以dp[2][2]2。验证一下以(2,2)为右下角、边长为2的正方形覆盖(1,1)(1,2)(2,1)(2,2)其中(1,1)是0所以边长2不成立最大应该是1。这里就出问题了。等等我算错了。dp[2][2]如果取三个邻居的最小值加1得到min(1,1,1)12但实际最大边长是1。这说明单纯取min1还不够还需要当前格子本身是1。在这个例子里(2,2)是1但为什么结果是2而不是1让我重新检查。矩阵(0,0)1 (0,1)1 (0,2)1 (1,0)1 (1,1)0 (1,2)1 (2,0)1 (2,1)1 (2,2)1dp[2][1]以(2,1)为右下角。检查边长2覆盖(1,0)(1,1)(2,0)(2,1)其中(1,1)0不成立。所以dp[2][1]1。dp[1][2]以(1,2)为右下角。边长2覆盖(0,1)(0,2)(1,1)(1,2)其中(1,1)0不成立。所以dp[1][2]1。dp[1][1]以(1,1)为右下角但(1,1)0所以dp[1][1]0。啊我漏了dp[1][1]0。所以min(1,1,0)11正确。这说明转移方程确实是取三个邻居的最小值加1而当前格子为0时直接为0。3.3 转移方程的严格表述综合上面的分析转移方程可以写成如果matrix[i][j] 0则dp[i][j] 0如果matrix[i][j] 1则dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1对于边界情况即i0或j0时dp[i][j]就等于matrix[i][j]的值是1则为1是0则为0因为第一行或第一列不可能构成边长大于1的正方形。为什么是取最小值加1直观理解是以(i,j)为右下角能构成的正方形受限于左边、上边、左上三个方向能提供的最大正方形。这三个方向中最小那个决定了短板加1是因为当前格子本身贡献了一层。这就像木桶效应最短的那块板决定了能装多少水。3.4 完整代码实现def maximal_square(matrix): if not matrix or not matrix[0]: return 0 rows, cols len(matrix), len(matrix[0]) dp [[0] * cols for _ in range(rows)] max_side 0 for i in range(rows): for j in range(cols): 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这段代码的时间复杂度是O(n·m)空间复杂度是O(n·m)。对于1000×1000的网格大约100万次操作瞬间完成。注意题目要求返回的是面积不是边长。很多人写完代码返回max_side结果答案差了一个平方。这个坑我踩过不止一次建议在函数最后统一做平方中间过程只维护边长。4. 空间优化从二维数组到一维滚动4.1 为什么可以压缩空间观察转移方程dp[i][j]只依赖于dp[i-1][j]上一行同列、dp[i][j-1]本行前一列、dp[i-1][j-1]上一行前一列。也就是说计算第i行时只需要第i-1行的数据更早的行完全用不到。这意味着我们可以用一个一维数组来滚动更新。但这里有一个细节dp[i-1][j-1]在更新dp[j]时会被覆盖掉所以需要用一个临时变量把它存起来。4.2 一维DP的实现细节def maximal_square_optimized(matrix): if not matrix or not matrix[0]: return 0 rows, cols len(matrix), len(matrix[0]) dp [0] * cols max_side 0 for i in range(rows): prev 0 # 相当于dp[i-1][j-1] for j in range(cols): temp dp[j] # 保存dp[i-1][j]因为接下来会被覆盖 if matrix[i][j] 1: if i 0 or j 0: dp[j] 1 else: dp[j] min(dp[j], dp[j-1], prev) 1 max_side max(max_side, dp[j]) else: dp[j] 0 prev temp # 更新prev为下一轮做准备 return max_side * max_side这里的关键是prev变量。在进入内层循环前prev初始为0对应第一列时dp[i-1][j-1]不存在的情况。每轮循环结束时把当前dp[j]的旧值即dp[i-1][j]赋给prev这样下一列计算时prev就正好是dp[i-1][j-1]。这个技巧我第一次写的时候绕了很久建议你拿纸笔画一下i1, j1时的数据流比看十遍代码都管用。4.3 空间优化的收益与代价空间从O(n·m)降到O(m)对于列数很大的矩阵内存占用显著降低。但代价是代码可读性下降prev变量的引入让逻辑不那么直观。在实际工程中如果内存不是瓶颈我通常优先写二维版本清晰易懂只有在内存受限或矩阵特别大时才切换到一维版本。另外一维版本还有一个隐藏的坑当matrix[i][j] 0时必须显式把dp[j]置0。如果漏了这一步dp[j]会保留上一行的值导致后续计算错误。这个bug很隐蔽因为在小矩阵上可能碰巧不出错。5. 边界条件与常见错误排查5.1 空矩阵和单行单列空矩阵直接返回0这个没什么争议。但单行或单列的情况容易出错。比如矩阵只有一行[1,1,1]最大正方形边长是1面积是1不是3。因为正方形要求行数和列数相等一行三列只能取1×1。在代码里当i0时dp[0][j]直接等于matrix[0][j]的值所以最大边长是1正确。单列同理。5.2 字符1和数字1的混淆输入矩阵的元素是字符0和1不是数字。如果你写成if matrix[i][j] 1在Python里永远为False因为字符1不等于数字1。这个错误在动态类型语言里不会报错只会默默返回0非常难查。我建议在函数开头加一个断言或者类型转换比如matrix [[int(c) for c in row] for row in matrix]把字符转成数字后续判断用 1。这样既避免了类型混淆也让代码更清晰。5.3 返回值的平方陷阱前面提过题目要的是面积。我见过不少人代码逻辑全对最后返回max_side结果答案差一个平方。建议在函数命名上就体现出来比如叫maximal_square_area提醒自己返回的是面积。5.4 遍历顺序不能反DP的遍历顺序必须是从左上到右下。如果你从右下到左上遍历dp[i-1][j]等子问题还没计算结果全错。这个错误在写代码时不容易犯但在面试手写代码时紧张之下有可能写反循环方向。5.5 一个完整的测试用例matrix [ [1,0,1,0,0], [1,0,1,1,1], [1,1,1,1,1], [1,0,0,1,0] ] print(maximal_square(matrix)) # 输出4这个矩阵中以(2,2)为右下角可以构成边长2的正方形面积4。你可以手动跑一遍DP表验证。6. 从最大正方形延伸出的变体题型6.1 最大矩形从正方形到矩形最大正方形是最大矩形的特例。最大矩形问题要求找出只包含1的最大矩形面积不要求是正方形。这道题的难度更高需要用单调栈来做时间复杂度O(n·m)。两者的区别在于正方形只需要一个维度边长矩形需要两个维度宽和高。所以正方形的DP状态是一维的矩形的DP需要额外维护高度信息。如果你能理解最大正方形的DP再去学最大矩形会容易很多。6.2 统计全1正方形的个数另一个常见变体是统计矩阵中全为1的正方形子矩阵的个数。这个问题的DP定义和最大正方形几乎一样只是最后不是取max而是把所有dp[i][j]加起来。因为dp[i][j]表示以(i,j)为右下角的最大正方形边长同时也等于以(i,j)为右下角的正方形个数边长为1到dp[i][j]各一个。这个性质很优美也是DP问题中状态值同时具有计数意义的典型案例。6.3 最大正方形在图像处理中的影子在图像处理领域有一个类似的问题叫最大连通区域或最大内接正方形。比如在二值图像中找最大的纯色正方形区域用于目标检测或特征提取。虽然具体算法可能用并查集或形态学操作但核心思想——利用局部信息递推全局最优——和最大正方形的DP是一致的。我在一个图像裁剪的小工具里就用过类似思路给定一张黑白掩码图找出最大的全白正方形区域用于确定裁剪框。当时直接用最大正方形的DP把1当作白色像素0当作黑色像素跑一遍就得到了最大内接正方形的边长和位置。6.4 变体题型的对比表格题型状态定义转移方程时间复杂度最大正方形以(i,j)为右下角的最大边长min(左,上,左上)1O(n·m)最大矩形以(i,j)为底的最大高度单调栈高度数组栈O(n·m)统计全1正方形同最大正方形累加所有dp值O(n·m)最大全1子矩阵同最大矩形同最大矩形O(n·m)这张表建议收藏面试前扫一眼能快速回忆起各题型的核心差异。7. 实操心得与性能调优建议7.1 用numpy加速大规模矩阵如果矩阵特别大比如10000×10000纯Python的循环会有点慢。这时候可以用numpy做向量化但DP的递推性质决定了它不容易直接向量化因为dp[i][j]依赖dp[i][j-1]同一行内有依赖。一个折中方案是用numba的JIT编译把双重循环编译成机器码速度能提升几十倍。我实测过一个5000×5000的全1矩阵纯Python大约跑8秒numba加速后不到0.2秒。from numba import jit import numpy as np jit(nopythonTrue) def maximal_square_numba(matrix): rows, cols matrix.shape dp np.zeros((rows, cols), dtypenp.int32) max_side 0 for i in range(rows): for j in range(cols): 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 if dp[i, j] max_side: max_side dp[i, j] return max_side * max_side注意numba对numpy数组的支持最好传入前先把字符矩阵转成int类型的numpy数组。7.2 提前终止的优化思路如果当前已经找到的最大边长是max_side那么在遍历时如果剩余的行数或列数不足以构成更大的正方形可以提前终止。比如当rows - i max_side时后面的行不可能产生更大的正方形直接break外层循环。这个优化在全1矩阵上效果不明显因为最大边长很快就到上限但在稀疏矩阵上能省不少时间。7.3 内存布局对缓存的影响二维DP数组按行优先存储时内层循环遍历列访问dp[i][j-1]是连续的缓存友好。如果按列优先存储访问会跳跃缓存命中率下降。Python的列表是行优先的所以内层循环遍历列是自然的选择。如果你用C或Java也要注意这一点。7.4 面试中的沟通要点如果这道题出现在面试中我建议的沟通顺序是先说出暴力解法并分析复杂度展示你有一个保底方案指出暴力解法的重复计算问题引出DP的必要性定义状态时明确说以(i,j)为右下角并解释为什么选右下角推导转移方程时画一个小例子辅助说明写完代码后主动提空间优化和边界情况这套流程走下来即使代码有小瑕疵面试官也能看到你清晰的思路。7.5 一个容易忽略的测试点很多人测试时只用全1矩阵或全0矩阵忽略了最大正方形不在右下角的情况。比如1 1 0 0 1 1 0 0 0 0 1 1 0 0 1 1最大正方形在左上角边长2。如果你的代码只在最后返回dp[rows-1][cols-1]就会得到错误答案。必须用一个变量在遍历过程中持续更新最大值。这个坑我在早期写代码时踩过当时测试用例恰好最大正方形在右下角代码通过了换了个用例就挂了。后来养成了习惯任何DP问题只要答案是取max或min就一定在遍历中维护全局最优而不是只看最后一个状态。8. 从这道题带走的通用DP思维最大正方形这道题表面上是找一个几何图形本质上是在训练一种思维方式如何用局部信息递推全局最优。这种思维在算法里叫动态规划在工程里叫增量计算在生活里叫站在巨人的肩膀上。我自己的体会是DP最难的不是写代码而是定义状态。状态定义对了转移方程往往水到渠成状态定义错了怎么推都别扭。最大正方形之所以经典是因为它的状态定义非常自然——以某个格子为右下角这个锚点选得好子问题天然满足无后效性。如果你正在准备算法面试我建议把这道题刷三遍第一遍理解思路第二遍手写二维DP第三遍写一维优化版本。三遍下来你对二维DP的掌控力会上一个台阶。之后再去碰最大矩形、编辑距离、最长公共子序列这些题会发现它们的内核是相通的。最后分享一个我常用的练习方法每做完一道DP题合上代码用白纸画出DP表手动填一遍。这个过程能暴露你对转移方程理解的盲区。比如最大正方形手动填表时你会真切感受到取最小值加1的几何含义比看十遍题解都深刻。