最大正方形——从暴力枚举到DP的木桶短板原理
最大正方形——从暴力枚举到DP的木桶短板原理
适读人群：Java后端工程师、二维DP学习者 | 阅读时长：约18分钟 | 难度：Medium
开篇故事
最大正方形这道题，我觉得是二维DP里"最有美感"的一道。
原因是它的状态转移方程本质上是一个"木桶短板"原理：一个正方形能扩大的边长，由它左、上、左上三个方向的最大正方形边长中最小的那个决定。
这个结论非常直觉，但我第一次做的时候还是没想出来，而是用了暴力枚举：对每个'1'的位置，枚举以它为右下角的所有正方形，逐个判断是否全为'1'。O(n^3)，超时了。
后来分析"为什么是取三者最小值"，反复画图验证，才真正理解了其中的道理。
今天从暴力解法出发，一步步推导出DP方程，让你真正理解这个"木桶短板"的来龙去脉。
一、题目解析
题号：LeetCode 221. Maximal Square
题目描述：在一个由 '0' 和 '1' 组成的二维矩阵内，找到只包含 '1' 的最大正方形，并返回其面积。
示例：
输入：
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
输出：4（最大正方形边长为2，面积为4）二、DP思路推导
2.1 暴力解法分析
对每个 '1' 的格子 (i, j)，以它为右下角，枚举边长 side 从1到 min(i,j)+1，判断是否存在全为'1'的 side×side 正方形。
时间复杂度 O(m×n×min(m,n))，在大矩阵上会超时。
2.2 DP状态定义
定义 dp[i][j] = 以格子 (i, j) 为右下角的最大全1正方形的边长
为什么选"右下角"？因为正方形的右下角唯一确定了一个正方形（加上边长），且右下角是我们从左上到右下遍历时最后到达的角，可以利用之前已经计算的结果。
2.3 状态转移方程推导（木桶短板）
考虑格子 (i, j) = '1' 时，以 (i, j) 为右下角的最大正方形。
要让这个正方形边长为 s，需要同时满足：
- 以 (i-1, j) 为右下角的最大正方形边长 >= s-1（上方）
- 以 (i, j-1) 为右下角的最大正方形边长 >= s-1（左方）
- 以 (i-1, j-1) 为右下角的最大正方形边长 >= s-1（左上方）
三个条件缺一不可。因此：
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1为什么是取最小值？
画图就清楚了：
假设 dp[i-1][j]=3（上方最大边长3），dp[i][j-1]=2（左方最大边长2），dp[i-1][j-1]=3（左上最大边长3）
那么以(i,j)为右下角，能形成的最大正方形边长是多少？
上方告诉我：(i-1,j)往左往上3格都是1（保证了右上角3×3是1）
左方告诉我：(i,j-1)往上往左2格都是1（保证了左下角3×2是1，但实际只有2列）
左上告诉我：(i-1,j-1)往左往上3格都是1
受限于左方只有2格，所以(i,j)能扩展到的最大正方形是 min(3,2,3)+1 = 3
形象理解：
- 上方决定了"能往上延伸多少行"
- 左方决定了"能往左延伸多少列"
- 左上角决定了"左上方是否有足够的1填充"
木桶的短板就是三者中最小的那个如果 matrix[i][j] = '0'，那么 dp[i][j] = 0（以0结尾的正方形边长为0）。
2.4 边界条件
- 第0行和第0列：dp[0][j] = matrix[0][j] - '0'，dp[i][0] = matrix[i][0] - '0'（边长只能是0或1）
2.5 状态转移示意
matrix：
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 2 2
1 0 0 1 0
最大值为2，面积=4 ✓三、解法一：标准二维DP
public class MaximalSquare {
/**
* 221. 最大正方形 - 二维DP
* 时间复杂度：O(m * n)
* 空间复杂度：O(m * n)
*/
public int maximalSquare(char[][] matrix) {
if (matrix == null || matrix.length == 0) return 0;
int m = matrix.length;
int n = matrix[0].length;
int[][] dp = new int[m][n];
int maxSide = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (matrix[i][j] == '0') {
dp[i][j] = 0;
} else if (i == 0 || j == 0) {
// 第0行或第0列，边长最多为1
dp[i][j] = 1;
} else {
// 木桶短板：取三个方向的最小值 + 1
dp[i][j] = Math.min(dp[i - 1][j],
Math.min(dp[i][j - 1], dp[i - 1][j - 1])) + 1;
}
maxSide = Math.max(maxSide, dp[i][j]);
}
}
return maxSide * maxSide; // 返回面积
}
}Mermaid木桶短板示意：
四、解法二：空间优化（一维滚动）
/**
* 221. 最大正方形 - 空间优化到O(n)
*/
public int maximalSquareOptimized(char[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int[] dp = new int[n];
int maxSide = 0;
int prev = 0; // 保存dp[i-1][j-1]（左上角值）
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int temp = dp[j]; // 保存dp[i-1][j]，下次迭代作为dp[i-1][j-1]
if (matrix[i][j] == '0' || i == 0 || j == 0) {
dp[j] = matrix[i][j] - '0';
} else {
dp[j] = Math.min(dp[j], Math.min(dp[j - 1], prev)) + 1;
// dp[j]此时是dp[i-1][j]，dp[j-1]已是dp[i][j-1]，prev是dp[i-1][j-1]
}
prev = temp;
maxSide = Math.max(maxSide, dp[j]);
}
prev = 0; // 每行开始时，prev（上一行的j=-1位置）重置为0
}
return maxSide * maxSide;
}五、举一反三
相关题目：
- LeetCode 1277. 统计全为1的正方形子矩阵：利用同样的dp，统计所有全为1的正方形数量（dp[i][j]即为以(i,j)为右下角的正方形数量）
- LeetCode 85. 最大矩形：最大正方形的"矩形版"，用单调栈（下篇详讲）
- LeetCode 764. 最大加号标志：变体
关键公式：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
这个公式可以用在任何"以当前格子为右下角的最大全1正方形"问题上。
六、踩坑实录
坑一：返回边长平方而不是边长
题目要求返回面积，是边长的平方。很多人直接返回 maxSide，忘记平方。
坑二：矩阵元素是char不是int
matrix[i][j] 是 '0' 或 '1'（字符），不是整数0或1。判断时用 == '1'，赋值时用 matrix[i][j] - '0'。
坑三：边界格子漏判
第0行和第0列的格子，dp值直接等于字符值（'1'=1，'0'=0），不能用三个方向的公式（会越界访问 dp[-1][j] 等）。
坑四：空间优化时prev的更新时机
每行开始时，prev应该重置为0（代表上一行的 j=-1 位置，即不存在，值为0）。如果不重置，第二行第一个元素的 prev 会用到第一行最后一个元素的值，结果出错。
七、总结
最大正方形的核心是"木桶短板"原理：
dp[i][j] = min(上, 左, 左上) + 1（当matrix[i][j]=='1'时）这个公式非常简洁，但推导需要理解为什么三者中最小的那个决定了边长上限。
| 解法 | 时间 | 空间 |
|---|---|---|
| 暴力枚举 | O(m×n×min(m,n)) | O(1) |
| 二维DP | O(m×n) | O(m×n) |
| 一维压缩 | O(m×n) | O(n) |