LeetCode 221 最大正方形：动态规划状态设计与转移方程详解

先聊点实在的：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] == '0'，dp[i][j] = 0。

还要注意边界行和边界列：当 i == 0 或 j == 0 时，dp[i][j] 最多只能是 1，因为边界上的正方形不可能向矩阵外扩展。所以代码里通常会把 dp 数组的维度设为 (m+1) x (n+1)，让 dp[1][1] 对应 matrix[0][0]，这样可以省去一堆 if 判断。

为什么这个转移是对的？想象你要扩大一个正方形的边长，从边长 k 扩到 k+1，那么以 (i, j) 为右下角的边长为 k+1 的正方形要成立，必须同时满足三个条件：

• 它的上方那块 (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] = 5，dp[i][j-1] = 3，dp[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 维度设成 (m+1) x (n+1)，下标从 1 开始，这样既能省掉边界判断，也让状态转移方程更整齐。注意 matrix 是字符数组，比较时要写 '1' 而不是 1。

C++ 版本：

class Solution { public: int maximalSquare(vector<vector<char>>& matrix) { if (matrix.empty()) return 0; int m = matrix.size(), n = matrix[0].size(); vector<vector<int>> dp(m + 1, vector<int>(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_side

Java 版本：

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(vector<vector<char>>& matrix) { if (matrix.empty()) return 0; int m = matrix.size(), n = matrix[0].size(); vector<int> 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 计算后依然是 1：

dp[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' 的最大边长就是连续长度。如果中间碰到 '0'，dp 归零，重新开始计数。

所以不需要特判第一行、第一列，虚拟边界把边界逻辑统一掉了。这也是我强烈推荐下标从 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 。如果你是用 C++11 之前的版本，得嵌套 min 写。Python 里 min 接受多个参数没问题。每次更新 dp[i][j] 之后要立刻更新 maxSide，不要等整个 dp 填完再扫描，那样虽然也能做，但多了一次 O(m * n) 遍历，完全没必要。我在本地测试时还遇到过一个问题：把 maxSide 初始化成负数，导致结果可能为 0，但全 '0' 矩阵本来就应该返回 0。正确初始化为 0 即可。

4.6 一口气全记住的速查表

5. 扩展思考：动态规划题目的通用方法论

5.1 如何快速确定状态

做完这道题，你可以沉淀一个 DP 建模方法论。遇到一个“求最大/最小/方案数”的二维网格问题，先把目标结果空间拆成以某个端点为中心/右下角/左上角的小问题。多数网格类 DP 的套路是 dp[i][j] 表示“以 (i, j) 为结尾/右下角的最优值”，因为递推方向可以借用已计算过的邻居。

做题时先问自己三个问题：最终答案落在哪个位置？如果我把答案缩小一个格子，它会落在哪里？这个格子能由哪些更小的格子推导出来？想清楚这三个问题，状态定义和转移方程基本就出来了。

LeetCode 221 就是典型：最终答案落在某个右下角；缩一格之后，大正方形里一定包含三个小正方形；所以转移方程里三个方向取 min。

5.2 DP常见题型和本题定位

动态规划的题型很多，常见的有线性 DP（爬楼梯、打家劫舍）、区间 DP（石子合并、最长回文子序列）、背包 DP（0/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 尤其适合这么画，因为你只需要三行三列就能完整复现所有转移方向。下次卡住的时候，不妨也拿笔画一画。