先聊点实在的LeetCode 221 这道 Maximal Square是我见过最适合用来理解“动态规划状态设计”的题目之一。它看着只是个二维矩阵里找最大正方形但你要是真用暴力去解写起来麻烦跑起来更难受可一旦你接受了“用右下角作为正方形锚点”这个视角整个转移方程会顺到连自己都惊讶。这道题适合所有刚接触动态规划、被一堆背包问题和区间DP绕晕的人也适合准备面试想快速复习基础套路的人。这篇文章我会从读题开始一步步把状态怎么定义、转移方程为什么长这样、代码怎么写最稳这些事讲透最后再把我自己踩过的坑和排查思路全部分享出来。1. 先读懂题目最大全1正方形到底在问什么1.1 题面与输入输出题目给的是一个 m x n 的二维矩阵矩阵里每个元素是字符 0 或 1。要求找出矩阵中只包含 1 的最大正方形面积返回这个面积值。注意它要的是正方形不是矩形面积在这道题里其实就是最大边长的平方。举个例子假设输入是1 0 1 0 0 1 0 1 1 1 1 1 1 1 1 1 0 0 1 0肉眼扫一下右下角那块由 (1,2) 到 (2,3) 围起来的 2x2 区域是全 1 的但更明显的最大全 1 正方形其实是中间 3 列和 2、3 两行交叉出来的那个 2x2不对我们再认真看。第二行有三列 1列 2、3、4第三行有五列 1列 0 到 4但第二行和第三行重叠且连续的 1 只有列 2、3、4所以能构成的最大正方形边长是 3位置在 (1,2) 到 (3,4)。答案面积就是 9。这个例子很有代表性它告诉你光看某一行、某一列有多少 1 没用必须同时满足行方向、列方向都能覆盖足够的长度而且所有交叉区域都得是 1这天然就是一个二维约束问题。1.2 为什么暴力法容易超时新手拿到这题第一反应往往是暴力枚举枚举每个可能的正方形起点左上角再枚举边长然后遍历正方形内部所有格子判断是否全是 1。这个做法的时间复杂度是 O(m * n * min(m, n)^2)最坏情况下一万个格子的矩阵直接就超时。就算你做点优化比如提前计算二维前缀和把“判断某个正方形是否全 1”降到 O(1)枚举起点的复杂度仍然是 O(m * n) 乘上 O(min(m, n)) 种边长整体 O(m * n * min(m, n))。在 m、n 都等于 200、300 时还能勉强跑但题目给到 300 以上再加上真正面试时面试官盯着你这种“差不多能过”的解法很难让人满意。更关键的是暴力法的思路缺少“复用”的智慧。你在判断一个 3x3 正方形时其实已经知道它里面的 2x2 子块是不是合法但暴力法会把这些信息全部丢掉每次都从零开始验证。动态规划解决的就是这类问题把已经算出来的小规模结论存起来让大规模判断直接建立在已有结论上。1.3 这题到底在考什么LeetCode 221 的核心考察点有三个。第一你能不能把一个几何问题抽象成可递推的数学模型第二你能不能定义出一种状态让这个状态之间存在明显的依赖关系第三你能不能通过状态转移把 O(m * n * min(m, n)) 的暴力复杂度降到 O(m * n)。说白了这题就是动态规划入门阶段“状态设计”的最佳练手题比背包问题更容易在图形上找到直觉也比简单的爬楼梯更能体现二维递推的威力。2. 从直觉到状态设计dp数组为什么这么定义2.1 把结果看成“以某个格子为右下角的正方形”做动态规划第一件事永远是找“子问题”。对这道题来说一个正方形由右下角确定之后其实它的位置就唯一确定了。换句话说“以 (i, j) 为右下角的最大全 1 正方形边长”就是一个清晰的子问题。为什么非要选右下角而不是左上角、中心点因为一旦确定了右下角往左上扩展的三个方向上、左、左上就变成了严格的小规模问题天然具有递推关系。如果你用左上角来定义扩展方向是右下那你就得依赖更大范围的未知状态这就不适合正向递推了。这里我打一个比方你要判断一块田里能不能种出方方正正的作物与其从田埂左上角开始量不如从右下角往回看——回头看刚才那三块地是不是都合格。这样每次只要参考已经验收过的三块地判断成本最低。2.2 dp[i][j]的数学定义我们定义dp[i][j] 以坐标 (i, j) 为右下角的最大全 1 正方形边长注意这是“边长”不是“面积”。很多人一开始会把 dp[i][j] 定义成面积结果状态转移还要开根号既麻烦又容易丢失精度。统一用边长最后返回 dp[i][j] 的最大值再平方即可。如果 matrix[i][j] 0那么以它为右下角的正方形边长一定是 0因为右下角本身已经是 0 了整个正方形不可能包含它。这一点是初始化的天然规则。如果 matrix[i][j] 1情况就值得仔细推敲了。2.3 转移方程的三个方向怎么来先给结论经典的转移方程是dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1但要求 matrix[i][j] 1。如果 matrix[i][j] 0dp[i][j] 0。还要注意边界行和边界列当 i 0 或 j 0 时dp[i][j] 最多只能是 1因为边界上的正方形不可能向矩阵外扩展。所以代码里通常会把 dp 数组的维度设为 (m1) x (n1)让 dp[1][1] 对应 matrix[0][0]这样可以省去一堆 if 判断。为什么这个转移是对的想象你要扩大一个正方形的边长从边长 k 扩到 k1那么以 (i, j) 为右下角的边长为 k1 的正方形要成立必须同时满足三个条件它的上方那块 (i-1, j) 作为右下角能覆盖边长至少 k 的全 1 正方形它的左方那块 (i, j-1) 作为右下角能覆盖边长至少 k 的全 1 正方形它的左上对角 (i-1, j-1) 作为右下角能覆盖边长至少 k 的全 1 正方形。你可以画个图以 (i, j) 为右下角的 2x2 格子左上看成是 (i-1, j-1) 的 1x1要扩成 3x3则需要 (i-1, j) 右侧那一列往上延展 2 格、(i, j-1) 下方那一行往左延展 2 格而这一切的核心是左上角的 2x2 区域必须完整。三个条件缺一不可所以能扩展的最大长度取决于三者的最小值加 1 之后就是当前格子能构成的最大边长。2.4 为什么只需要看三者最小值这是整个动态规划解法里最重要的一个“为什么”很多题解一句话带过但初学者经常卡在这里。假设 dp[i-1][j] 5dp[i][j-1] 3dp[i-1][j-1] 4。以 (i, j) 为右下角能扩出边长多少的正方形答案是 4也就是三者最小值再加 1即 4。因为 dp[i-1][j] 再大也只说明竖直方向很宽裕dp[i][j-1]3 已经限制了水平方向往左最多只能覆盖 3 个格子你不可能要求左边那行在横向上多出一个格子来——它们本来就是 0。而 dp[i-1][j-1]4 又限制了左上角的方块区域只有 4 的边长所以你最多只能拼出一个 4x4 的方块。我用一个极端的例子解释假设某一行左边只有一个 1右边全是 1但从上往下三行里第一个位置恰好是 0。那么不管右下角能往上延伸多少水平方向如果被 0 截断能组成的正方形边长仍然很小。取最小值就是在“短板效应”下保证三维上、左、左上都满足。这个思路非常像搭积木你能搭多高的柱子不取决于最高的那根而取决于最矮的那根。动态规划里取 min 的操作本质上就是在算“共同约束”。3. 代码实现二维DP与一维滚动优化3.1 二维DP写法C / Python / Java先看最直观的二维DP。我习惯在代码里把 dp 维度设成 (m1) x (n1)下标从 1 开始这样既能省掉边界判断也让状态转移方程更整齐。注意 matrix 是字符数组比较时要写 1 而不是 1。C 版本class Solution { public: int maximalSquare(vectorvectorchar matrix) { if (matrix.empty()) return 0; int m matrix.size(), n matrix[0].size(); vectorvectorint dp(m 1, vectorint(n 1, 0)); int maxSide 0; for (int i 1; i m; i) { for (int j 1; j n; j) { 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; maxSide max(maxSide, dp[i][j]); } } } return maxSide * maxSide; } };Python 版本class Solution: def maximalSquare(self, matrix: List[List[str]]) - int: if not matrix: return 0 m, n len(matrix), len(matrix[0]) dp [[0] * (n 1) for _ in range(m 1)] max_side 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 max_side max(max_side, dp[i][j]) return max_side * max_sideJava 版本class Solution { public int maximalSquare(char[][] matrix) { if (matrix.length 0) return 0; int m matrix.length, n matrix[0].length; int[][] dp new int[m 1][n 1]; int maxSide 0; for (int i 1; i m; i) { for (int j 1; j n; j) { if (matrix[i - 1][j - 1] 1) { 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]); } } } return maxSide * maxSide; } }这里的 min 嵌套不需要额外头文件语言标准库里都有支持。Java 里没有直接的 min 三参数重载所以用两次 Math.min 嵌套。3.2 空间优化为什么能压成一维二维 dp 可以进一步压成一维数组。因为 dp[i][j] 只依赖三个值左边 dp[i][j-1]、上方 dp[i-1][j]、左上对角线 dp[i-1][j-1]。在更新第 i 行时一维数组里存的是第 i-1 行的数据dp[j-1] 在本次更新之前就已经变成了第 i 行的值所以它对应 dp[i][j-1]dp[j] 在更新前还是第 i-1 行的值对应 dp[i-1][j]而左上角 dp[i-1][j-1] 需要用一个额外变量提前保存下来否则它会被当前行的 dp[j-1] 覆盖掉。具体做法是在每轮内层循环开始前用变量 prev 记录 dp[j-1]还没被覆盖的旧值。更新 dp[j] 前把 dp[j] 的旧值存到 nextPrev用于下一轮循环。一维 C 版本class Solution { public: int maximalSquare(vectorvectorchar matrix) { if (matrix.empty()) return 0; int m matrix.size(), n matrix[0].size(); vectorint dp(n 1, 0); int maxSide 0; for (int i 1; i m; i) { int prev 0; for (int j 1; j n; j) { int temp dp[j]; if (matrix[i-1][j-1] 1) { dp[j] min({dp[j], dp[j-1], prev}) 1; maxSide max(maxSide, dp[j]); } else { dp[j] 0; } prev temp; } } return maxSide * maxSide; } };这个写法里最难理解的就是 prev 和 temp。我每次写的时候都会心里念一遍temp 保存的是当前 dp[j] 更新前的值也就是这一行上一轮留下的 dp[j]但它代表的是上一行的第 j 列prev 保存的是本轮已经更新过的 dp[j-1] 的旧值也就是左上角位置。如果你在纸上把一维数组的更新过程像走格子一样画一遍这个逻辑会变得非常清晰。3.3 边界条件与初始化细节初始化时 dp 全为 0这对应的是矩阵外的一圈虚拟边界。因为矩阵外的格子不可能构成正方形所以初始边长全为 0。当 matrix[i-1][j-1] 1 且 i-1 0 或 j-1 0 时dp[i][j] 经过 min 计算后依然是 1dp[1][j] min(dp[0][j], dp[1][j-1], dp[0][j-1]) 1由于 dp[0][*] 0而 dp[1][j-1] 如果第一行全是 1它会从 1、2、3... 这样累加这正好是正确的第一行连续 1 的最大边长就是连续长度。如果中间碰到 0dp 归零重新开始计数。所以不需要特判第一行、第一列虚拟边界把边界逻辑统一掉了。这也是我强烈推荐下标从 1 开始的原因代码更短bug 更少。3.4 时间复杂度与空间复杂度分析二维版本的时间复杂度为 O(m * n)空间复杂度 O(m * n)。一维滚动优化后时间复杂度不变空间复杂度降到 O(n)。这里只说空间是 O(n) 而不是 O(min(m, n))是因为我们压缩的是列维度。理论上你也可以选择把行和列对调让空间变成 O(m)但通常没必要因为题目给的 m、n 差不多大时两者没有明显差别。不过如果矩阵极端瘦长比如 10000 行 2 列那压缩列维度 O(2) 显然比 O(10000) 更划算反之如果是 2 行 10000 列你应该考虑转置或先判断 m、n 大小来选择压缩方向。实际笔试里很少会犟到这一步但面试时主动提一句“我可以根据行列大小选择压缩方向”会加分。4. 做题时容易踩的坑4.1 字符 1 和数字 1 搞混这是 LeetCode 上非常经典的“低级错误”。矩阵元素是字符串 1 或 0不是整数。你要是写 if (matrix[i-1][j-1] 1)编译器不会报错字符会被隐式转换成 ASCII 码 49但逻辑完全错误最终结果永远是 0。所有比较都要写成 1。Python 也一样矩阵是 List[List[str]]不是数字矩阵需要用 matrix[i - 1][j - 1] 1。4.2 返回面积还是边长题目问的是“面积”。很多人在 dp 转移时算的是边长最后却直接 return maxSide导致结果差了平方。LeetCode 221 的答案是边长平方不是边长本身。这个坑我在面试模拟里见过不止一次建议在变量名上就区分明白比如 maxSide 表示边长最后 return maxSide * maxSide。4.3 一维数组更新方向写反如果你已经会做 01 背包可能形成一种条件反射一维数组要从后往前更新避免覆盖。但 Maximal Square 的一维优化是从前往后更新的因为当前行的 dp[j] 依赖于当前行的 dp[j-1]左边如果从后往前更新当你算 dp[j] 时dp[j-1] 还是上一行的旧值左边信息就丢了。这一点跟背包问题的优化方向正好相反是真正的易错点。为什么背包要从后往前而这里从前往后因为背包每个物品只能用一次更新 dp[j] 时依赖的是“不含当前物品”的旧状态必须保证 dp[j-weight] 没被当前物品污染而这道题的 dp[j] 需要的是“同一行已经扫过的左边状态”所以反而需要从左到右传播。把两个题放一起对比着记印象更深刻。4.4 空矩阵和空行题目给的 matrix 有可能为空matrix[0] 也可能为空。如果上来就取 matrix[0].size()第二个情况直接越界或未定义行为。稳妥做法是先判 matrix.empty()再判 matrix[0].empty()。这道题的测试用例很贴心有空矩阵的用例但你自己写的时候不能依赖测试用例帮你发现。4.5 最小值初始化和最大值更新位置用 C 的 min({a, b, c}) 时要确保 include 。如果你是用 C11 之前的版本得嵌套 min 写。Python 里 min 接受多个参数没问题。每次更新 dp[i][j] 之后要立刻更新 maxSide不要等整个 dp 填完再扫描那样虽然也能做但多了一次 O(m * n) 遍历完全没必要。我在本地测试时还遇到过一个问题把 maxSide 初始化成负数导致结果可能为 0但全 0 矩阵本来就应该返回 0。正确初始化为 0 即可。4.6 一口气全记住的速查表常见错误错误表现正确做法字符比较写成数字答案恒为 0用 1 比较返回边长而非面积结果偏小maxSide * maxSide一维数组更新方向写反答案偏小或随机从左到右更新未处理空矩阵运行时错误先判空再取行列dp 下标不从 1 开始边界 if 太多用虚拟边界min 的三参数写法在旧版编译环境不支持编译错误用嵌套 min5. 扩展思考动态规划题目的通用方法论5.1 如何快速确定状态做完这道题你可以沉淀一个 DP 建模方法论。遇到一个“求最大/最小/方案数”的二维网格问题先把目标结果空间拆成以某个端点为中心/右下角/左上角的小问题。多数网格类 DP 的套路是 dp[i][j] 表示“以 (i, j) 为结尾/右下角的最优值”因为递推方向可以借用已计算过的邻居。做题时先问自己三个问题最终答案落在哪个位置如果我把答案缩小一个格子它会落在哪里这个格子能由哪些更小的格子推导出来想清楚这三个问题状态定义和转移方程基本就出来了。LeetCode 221 就是典型最终答案落在某个右下角缩一格之后大正方形里一定包含三个小正方形所以转移方程里三个方向取 min。5.2 DP常见题型和本题定位动态规划的题型很多常见的有线性 DP爬楼梯、打家劫舍、区间 DP石子合并、最长回文子序列、背包 DP0/1 背包、完全背包、树形 DP树的直径、状态压缩 DP旅行商问题。Maximal Square 属于二维网格 DP跟 64 最小路径和、1277 统计全为 1 的正方形子矩阵共享一套方法论。有人问 KMP 算法属不属于动态规划严格说 KMP 失败回退表的构建过程有 DP 的影子但它通常被归类为字符串匹配算法在刷题时不需要纠结分类关键是理解“用已知状态推导新状态”的思想。如果你是刚学动态规划我的建议是不要一上来就冲背包和区间 DP先在二维网格题上建立“状态 转移”的图形直觉。Min Path Sum、Maximal Square、Unique Paths 这三道题做完你对 dp 数组下标含义、转移方向、初始化边界这些基本功会扎实很多。5.3 继续刷题建议如果你把 221 做完觉得意犹未尽可以顺着这三个方向延伸同类型的计数题LeetCode 1277 Count Square Submatrices with All Ones。它要统计所有全 1 正方形的数量而不仅仅是最大面积其实用到的 dp 定义几乎一样只是统计时累加所有 dp[i][j] 的值。矩形版本LeetCode 85 Maximal Rectangle。最大全 1 矩形比正方形难解法是把每一行当成柱状图再用单调栈求最大矩形面积这已经进入“DP 数据结构”组合题了。如果矩阵里的值不是 0/1 而是任意权重正方形怎么做这时 DP 就不够用了得用前缀和加二分这是另一条线。路线可以这么铺221 → 1277 → 85由正方形到矩形由简单 DP 到单调栈难度递增知识重叠度高非常适合连续刷。我也是这么一路刷过来的每次回头看 221 都会感慨它真的是一道“小身材、大能量”的题。最后再分享一个我个人的体会遇到 DP 题不要急着写代码先在草稿纸上画一个 3x3 的小矩阵把 dp 值一个个手算填出来。这个动作看起来慢但比盲写十遍代码都管用。我教过不少朋友他们在纸上画完一遍转移过程之后写代码就再也没出过错。LeetCode 221 尤其适合这么画因为你只需要三行三列就能完整复现所有转移方向。下次卡住的时候不妨也拿笔画一画。
