上周有个读者来问我说自己在某大厂二面时被问到 LeetCode 221 最大正方形这道题手写动态规划写到一半卡住了dp 数组的递推公式推不出来最后只能草草收场。这道题确实很有代表性它看起来是个简单的二维动态规划但真正动手写的时候很多人会卡在状态定义和边界处理上。这篇文章我把这道题从头到尾拆一遍包括暴力解法的思路、动态规划的推导过程、Java 和 Python 的完整实现以及空间优化的细节最后再聊聊面试中常见的变形题和坑点。不管你是在准备算法面试还是单纯想把动态规划的基础打牢这篇内容都能给你一些参考。1. 这题到底在考什么审题与暴力解法1.1 先看清楚题目再说“简单”LeetCode 221 的原题描述很简洁给你一个由0和1组成的二维矩阵你需要找到其中只包含1的最大正方形并返回它的面积。注意几个关键词第一个是“正方形”不是矩形所以边长必须是相等的第二个是“只包含1”也就是整个正方形内部不能有任何一个0第三个是返回面积不是边长。很多人在面试时第一步就栽在审题上。这道题给的是字符数组char[][]不是整数数组所以判断某个位置是不是1时要用字符比较matrix[i][j] 1。如果你心里默认它是int[][]直接写成matrix[i][j] 1代码跑起来全错这是一类非常隐蔽的低级错误。另外一个容易忽略的细节是空输入如果矩阵是char[][]的引用为null或者行数为 0、列数为 0都应该直接返回 0不处理的话后面访问matrix[0]会直接抛空指针或数组越界异常。“最大正方形”这个名词本身也容易被误解成“最大面积的闭合区域”但题目要求的其实是“完全由1构成的、四条边平行于矩阵边界的正方形”。左上角到右下角方向的斜正方形、旋转后的正方形都不在考虑范围内因为矩阵本身是规则的题目隐含了边与矩阵坐标轴对齐这个前提。理解清楚这一点后续的状态转移方程才不会跑偏。1.2 暴力解法能想出来但大概率过不了先不要急着上动态规划把暴力解法想清楚往往能帮助你理解为什么需要动态规划。暴力解法的思路很直接遍历矩阵中每一个值为1的格子以这个格子作为正方形的左上角然后尝试向外扩展边长。假设当前格子坐标为(i, j)先检查边长 1 是否成立也就是这个格子本身是1然后检查边长 2也就是以(i, j)到(i1, j1)这个 2x2 区域是否全是1边长 3 同理。每次扩展边长前都要遍历新增的那一行和那一列确认这些格子都是1只要出现一个0就停止扩展。写成伪代码大概是这样的def maximal_square_brute_force(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: side 1 flag True while i side rows and j side cols and flag: for x in range(i, i side 1): if matrix[x][j side] 0: flag False break for y in range(j, j side 1): if matrix[i side][y] 0: flag False break if flag: side 1 max_side max(max_side, side) return max_side * max_side这个解法的时间复杂度是 O(m × n × min(m, n)²)其中 m 和 n 是矩阵的行数和列数。为什么是这么高的复杂度因为外层遍历 m×n 个格子每个格子最多向外扩展 min(m, n) 次边长每次扩展都要扫描当前边长对应的一整行和一整列加起来就是平方级别的额外开销。我一个朋友用 Python 写了这个版本在 LeetCode 提交后直接超时因为题目的测试数据最大能到 300×300这个数量级下暴力解法是撑不住的。暴力解法虽然有性能问题但它给了我们一个重要启发判断一个格子是否能扩展成更大的正方形本质上是在反复扫描同一个区域里的格子存在大量的重复计算。动态规划的切入点就是把“某个区域是否全是1”这个信息提前记录下来用空间换时间。2. 动态规划思路拆解为什么是 dp[i][j]2.1 状态定义以“右下角”为锚点动态规划第一步永远是定义状态。最大正方形这题最常见的状态定义是dp[i][j]表示以(i, j)为右下角、且全由1构成的正方形的最大边长。你可能要问为什么非要选右下角而不是左上角这其实是动态规划的经典思路每个状态依赖的是“更小规模”的子问题。如果以左上角为锚点向外扩展你很难复用已经算好的信息因为你不知道以左上角为中心的区域内部是否全是1扩展时还得重新扫描整块区域。而如果以右下角为锚点往回看一个以(i, j)为右下角的正方形去掉右边一列和下边一行之后剩下的部分恰好可以对应到(i-1, j)、(i, j-1)、(i-1, j-1)这三个位置上的子正方形。这个性质直接给了我们递推的空间。用生活化的类比来解释想象你站在一个广场的右下角想知道以你为右下角的最大正方形有多大。你不能只看脚尖那一块得看看你左边的朋友能站多大正方形、上边的朋友能站多大正方形以及左上方那位“前辈”能站多大正方形。三个方向中最小的一块决定了你能以多大规模的方阵站进去。2.2 转移方程是怎么来的有了状态定义接下来推导转移方程。假设matrix[i][j] 1那么dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1。如果matrix[i][j] 0那么dp[i][j] 0。为什么取三者最小值再加 1我们可以反过来思考如果dp[i][j]的值为 k这意味着以(i, j)为右下角存在一个边长为 k 的全 1 正方形。那么这个正方形必然包含以(i-1, j)为右下角、边长为 k-1 的正方形同时包含以(i, j-1)为右下角、边长为 k-1 的正方形也包含以(i-1, j-1)为右下角、边长为 k-1 的正方形。换句话说这三个位置上各自的dp值至少是 k-1。反过来当你知道这三个dp值分别是dp[i-1][j]、dp[i][j-1]、dp[i-1][j-1]时它们中最小值若是 t那么这三个位置都至少能提供边长为 t 的全 1 正方形。把这三块区域叠在一起再加上右下角当前格子这个1正好拼出一个边长为 t1 的全 1 正方形。所以转移方程就是三者最小值加 1。这里有一个关键细节为什么是三个方向而不是两个有些初学者会想既然只要判断左边和上边为什么不取min(dp[i-1][j], dp[i][j-1]) 1因为有角。如果只考虑左边和上边你无法保证左上角那块区域是完整的1会导致缺角的“劣质正方形”被误判。看下面这个例子矩阵为三行三列中间那个位置如果只看左边和上边会得到一个边长为 2 的假正方形但实际上中间有0破了局。三方向取最小值就是为了保证整个矩阵块完整。2.3 初始化和遍历顺序dp数组的初始化分为两种情况。第一行和第一列的格子如果matrix[i][j] 1那么dp[i][j] 1如果是0则dp[i][j] 0。因为第一行和第一列的上方或左方不存在根本形不成边长为 2 及以上的正方形。这部分可以单独初始化也可以在遍历时统一处理只要保证索引不越界。遍历顺序上我们按行从上到下、列从左到右扫描。因为dp[i][j]依赖dp[i-1][j]上一行、dp[i][j-1]当前行左侧和dp[i-1][j-1]上一行左侧只有按行从左到右按列从上到下遍历才能保证这三个依赖位置都已经被计算过。如果反过来从下往上遍历依赖方向被打破结果必然是错的。做动态规划题目时养成一个习惯先画出依赖关系再决定遍历方向。这个习惯比死记硬背一百道题都有用。手动推演一个小例子很有帮助。假设矩阵是1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0按行填充 dp 表第一行为1 0 1 0 0第二行为1 0 1 1 1这里第二行第三列是1它的上方是1左方是1左上方也是1三者最小值为 1所以 dp 值为 2表示以这个格子为右下角存在边长 2 的正方形。你可以在草稿纸上把整个 dp 表填完这个过程会帮你建立非常直观的感受也能迅速发现自己的错误。3. 代码落地从伪代码到 AC 的完整过程3.1 标准二维 DP 实现Java 版我先把最直观的二维 DP 版本写出来Java 代码可以作为面试时的手写参考public int maximalSquare(char[][] matrix) { if (matrix null || matrix.length 0 || matrix[0] null || matrix[0].length 0) { return 0; } int rows matrix.length; int cols matrix[0].length; int[][] dp new int[rows][cols]; int maxSide 0; for (int i 0; i rows; i) { for (int j 0; j cols; j) { if (matrix[i][j] 1) { if (i 0 || j 0) { dp[i][j] 1; } else { dp[i][j] Math.min(Math.min(dp[i - 1][j], dp[i][j - 1]), dp[i - 1][j - 1]) 1; } maxSide Math.max(maxSide, dp[i][j]); } else { dp[i][j] 0; } } } return maxSide * maxSide; }这段代码有几个需要强调的地方。第一边界判断写全了matrix[0]也要判空否则传一个char[][]为空但第一行引用为 null 的输入照样崩。第二初始化没有单独开循环而是在主循环里用i 0 || j 0判断处理代码更简洁逻辑也更集中。第三maxSide在每次更新 dp 值后同步更新最后返回的是边长的平方。时间复杂度 O(m × n)空间复杂度 O(m × n)其中 m 是行数n 是列数。这个版本已经可以通过 LeetCode 的全部测试用例用时在 5ms 左右表现稳定。从面试角度来说写出这个版本已经能拿到基础分了。3.2 Python 版本有时候要注意深拷贝陷阱Python 选手最常踩的坑是初始化二维列表时写成了[[0] * cols] * rows。这个写法看起来没问题但乘出来的每一行都是同一个列表对象的引用修改一个格子会导致一整列跟着变。正确写法是用列表推导式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_sidePython 的min函数一次可以接收三个参数写起来比 Java 舒服不少。测试的时候建议大家用[[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]这个官方例子跑一遍期望输出是 4对应右下角那片 2x2 的区域。跑通了之后再把矩阵整体换成全1的 3x3 矩阵输出应该是 9。3.3 空间优化一维滚动数组的精髓dp[i][j]只依赖当前行的左边一格dp[i][j-1]、上一行的同列dp[i-1][j]和上一行的左列dp[i-1][j-1]也就是说计算第 i 行时我们只需要第 i-1 行的数据更早的行完全用不上了。这时候可以用一个长度为 cols 的一维数组把空间复杂度压到 O(n)。关键问题来了怎么在滚动数组里同时拿到三个方向的值从左到右遍历时dp[j]在更新前保存的是dp[i-1][j]的旧值dp[j-1]在更新后保存的是dp[i][j-1]的新值。那dp[i-1][j-1]呢在dp[j]还没被覆盖时它存在dp[j-1]里但等你更新dp[j]时dp[j-1]已经变成当前行的值了。所以必须在更新前用一个临时变量把旧的dp[j-1]存下来。正确写法如下public int maximalSquareOptimized(char[][] matrix) { if (matrix null || matrix.length 0 || matrix[0].length 0) { return 0; } int cols matrix[0].length; int[] dp new int[cols]; int maxSide 0; int prev 0; for (int i 0; i matrix.length; i) { for (int j 0; j cols; j) { int temp dp[j]; if (matrix[i][j] 1) { if (i 0 || j 0) { dp[j] 1; } else { dp[j] Math.min(Math.min(dp[j], prev), dp[j - 1]) 1; } maxSide Math.max(maxSide, dp[j]); } else { dp[j] 0; } prev temp; } } return maxSide * maxSide; }这里prev保存的是本轮更新前dp[j]的值也就是上一行第 j 列的旧值。等到计算下一列时dp[j-1]已经存了当前行的最新值而prev里存的正是上一行第 j 列的值它会在下一轮被用作“左上角”的参考。这个变量设计是滚动数组版本最核心的细节面试时如果被问到底层为什么能这么优化你需要能讲清楚这一步。空间优化版本的用时和二维版本差不多但内存占用明显降低。对于 300×300 的矩阵二维数组要开 720000 个整数一维数组只要 300 个差距还是很明显的。我在实际测试中二维版本内存占用约 39MB优化后约 20MB效果肉眼可见。3.4 复杂度对比一张表看清差异解法时间复杂度空间复杂度代码量适用场景暴力解法O(m × n × min(m,n²))O(1)较短小矩阵、思路演示二维 DPO(m × n)O(m × n)中等常规面试、系统设计滚动数组 DPO(m × n)O(n)稍长大矩阵、空间受限场景从面试官的角度看如果你能先给出二维 DP 版本再主动提出“空间还可以优化到 O(n)”这是一个很好的加分项。从工程角度看实际业务中矩阵规模如果不大二维版本可读性更好维护成本更低如果数据量很大比如像素矩阵、地理栅格数据滚动数组就是必须考虑的方向。4. 高频坑点、面试追问与调试技巧4.1 我踩过的那些坑第一个坑是字符和数字混淆。题目给的是char[][]矩阵里的元素是字符1和0不是整数 1 和 0。写matrix[i][j] 1看起来合理跑起来全是 false因为字符1的 ASCII 值是 49整型 1 根本不相等。这问题如果不跑一遍测试基本发现不了白花半小时排查。第二个坑是滚动数组的第二层循环方向。前面给出的优化版本第二层循环是从左到右如果你不小心写成从右到左dp[j-1]会读取到上一行旧值导致整个递推关系错乱。我最初优化空间时就是顺手写了for (int j cols - 1; j 0; j--)结果出来的最大面积比正确答案大因为旧值被反复使用放大了结果。记住规则如果依赖左边元素就从左往右遍历如果依赖右边元素就从右往左遍历。Max Square 这题依赖左边所以必须从左往右。第三个坑是边界情况没考虑。空矩阵、单行矩阵、单列矩阵这三种情况我在第一次提交时漏掉了单行单列导致访问dp[i-1]时越界。LeetCode 的测试虽然有不少边界用例但自己提前写好保护逻辑总比碰运气强。建议所有矩阵类的动态规划题都先写一个统一的判空逻辑if (matrix null || matrix.length 0 || matrix[0] null || matrix[0].length 0) { return 0; }4.2 面试官最喜欢问的三个变形题有经验的面试官不会让你只写这一道题他们通常会在此基础上做变形。第一个变形是“如果要求返回最大正方形的左上角坐标和边长怎么改”。这个很简单在更新maxSide时同时记录当前的(i, j)坐标最后返回(i - maxSide 1, j - maxSide 1)和maxSide。注意边界坐标计算时要加 1因为 dp 存的是边长。第二个变形是“如果要求最大矩形的面积怎么解”。这就是 LeetCode 85解法不再是简单的min(dp 三方向) 1而是用柱状图 单调栈或者动态规划统计每一行上方连续 1 的高度然后求柱状图的最大矩形。这道题比最大正方形难一档面试官通常会在你写出正方形解法之后顺势问“如果放宽条件变成矩形呢”用来考察你的举一反三能力。我的建议是至少理解柱状图法的思路能在面试现场推导出来这比背代码更有说服力。第三个变形是“如果是求最大连通区域面积怎么解”。这就变成图的问题了用 BFS/DFS 或并查集处理跟动态规划基本不搭边了。面试官这样问通常是想看你能否区分“几何规则图形”和“自由连通区域”在算法策略上的差异不需要真的写代码能说出思路就可以。4.3 调试技巧把 dp 表画出来真的有用如果你写完了代码但结果不对最快的方式是在循环里打印 dp 表。我第一次刷这题时怎么调都不对后来加了两行打印把每次循环后的dp[j]输出来立刻发现第三行第二列的位置 dp 值异常大原因是滚动数组的prev传递出了问题。打印 dp 表能帮你把抽象的动态规划过程具体化强烈建议调试时用一下。还有一个经验不要只跑 LeetCode 自带用例自己构造几组特殊数据。比如全1的 5x5 矩阵答案应该是 25全0的矩阵答案应该是 0只有对角线上有1的矩阵答案应该是 1。这些用例能有效验证递推公式在不同场景下的正确性。我每次讲动态规划都会建议读者自建一个包含五到六个用例的测试文件不靠在线评测系统排查问题效率会高很多。4.4 从面试角度多说几句这道题是个典型的“会者不难”的题目。能写出二维 DP 版本的人很多但能把为什么取三方向最小值讲清楚、能把空间优化原理说明白、能在变形题里快速迁移思路的人并不多。面试时我会建议你按这个顺序组织表达先讲暴力解法及复杂度不足再引出动态规划的状态定义然后推导转移方程最后写代码和做空间优化。整个过程中口述推导比闷头写代码重要得多。面试官真正想看的是你面对一个陌生问题的思维路径而不是背题能力。我自己在陪朋友 mock 面试时发现很多人卡在“为什么是右下角而不是左上角”这个问题上。我的建议是拿一个 3x3 的小矩阵手动把两种锚点的推演过程各画一遍你会发现右下角锚点的递推关系非常自然往前走一步就是子问题而左上角锚点需要每步检查新增的行列结构上天然适合暴力而非 DP。这种对比感受一旦建立就再也不容易忘了。