LeetCode 221中等二维 DP
最大正方形 图解题解
这道题到底在问什么
给一个只含 0 和 1 的矩阵，找出只由 1 组成的最大正方形，返回它的面积。
- matrix
- 4×4，右下角藏着一块 3×3 的 1
- 输出
- 9（边长 3，面积 3×3）
先想最直接的笨办法
换个记法：让 dp[i][j] 记住「以这个格子作右下角，能撑出的最大正方形边长」。这样每个格子只算一次、还能借用左、上、左上三个邻居已经算好的结果——这正是上面笨办法重复扫的那部分，现在全省下来。（动画第 4 步）
最优解：一步一步想明白
- 3最直接的想法：把每个格子都当正方形的右下角，再一圈一圈往外扩，每扩一层都要把那一整圈格子重新检查一遍是不是全 1。格子多、边长大时，同一片区域被反复扫，慢得离谱。痛点在于：相邻格子的检查结果被白白丢掉、每次都从头来。
- 4换个记法：让 dp[i][j] 记住「以这个格子作右下角，能撑出的最大正方形边长」。这样每个格子只算一次、还能借用左、上、左上三个邻居已经算好的结果——这正是上面笨办法重复扫的那部分，现在全省下来。
- 5如果当前格自己是 1，想让它当一个边长 3 正方形的右下角，那它正左边、正上边、左上角这三个格子，必须各自都能当一个边长 2 正方形的右下角——三块边长 2 的正方形加上当前格，刚好严丝合缝拼成边长 3。只要有一个邻居撑不到，就拼不齐。所以当前边长被三个邻居里最小的那个决定。
- 6matrix 摆上台，dp 表先全空这是要处理的 4×4 矩阵（formula 那行列出每行的 0/1）。咱再开一张同样大小的 dp 表，先全空，等会儿从左上往右下一格一格填，每格填「以它为右下角的最大正方形边长」。
- 7边上的格子最多撑边长 1最上面一行和最左边一列没有完整的左、上、左上三个邻居，撑不出更大的正方形。所以规则很简单：原格是 1 就填 1，是 0 就填 0。注意行0列2、行2列0这两个 0 原样填 0。
- 8三邻居 = 上1 左1 左上1，取最小来到 (1,1)，原格是 1。看它的三个邻居：上=1、左=1、左上=1，三个都至少 1。取最小值 1 再 +1，所以这一格能撑边长 2。
- 9dp[1][1] = 2把 2 填进 (1,1)。这个 2 不是凭空来的：它说「以我为右下角，左、上、左上各借一格，正好围出一块 2×2 全 1 的正方形」。best 边长更新成 2。
- 10继续向右下推进继续一格格往右、往下填。提醒一处：行1列2上面原矩阵那块有个 0（行0列2=0），所以 (1,2) 的「上邻居」是 0，min 一拉就只有 1——一个 0 邻居会把正方形死死按在边长 1。表填到行2，已经看到 (2,2)=2，又一块 2×2。
- 11三邻居 = 上1 左2 左上1 → min=1这是全题最该停下看的一帧。(2,3) 自己是 1，左邻居已经是 2，看着像要长到 3 了——可上邻居只有 1、左上也只有 1。木桶装多少水看最短那块板：min(1,2,1)+1 只能是 2。一个邻居拖后腿，整块正方形就长不大。
- 12三邻居 = 上2 左2 左上2 → min=2填到右下角 (3,3)，原格是 1。这次三个邻居上=2、左=2、左上=2整整齐齐，三块 2×2 加自己，min(2,2,2)+1 = 3！这是第一次有格子撑到边长 3。
- 13best = 3 → 返回 3×3 = 9整张表填完，里面最大的数字是 (3,3) 的 3，就是全矩阵能拼出的最大正方形边长。题目要面积，所以边长平方：3×3 = 9。注意返回的是 best 平方，不是 best 本身。
- 16一句话记住这题：dp[i][j] = min(三个邻居) + 1。木桶能装多少水看最短的板，正方形能撑多大看最弱的邻居。
- 21记牢「以右下角为状态 + 取邻居最小 + 边界即地基」这套路，就能往上爬：最大长方形（85，转单调栈）、统计全 1 子矩形个数（1277，把 dp 值直接累加）。卡住时点开右侧小欧 AI 私教问一句「为什么这里用 min」，或去通关训练里找同款二维 DP 连刷几道。
⚠️ 容易写错的地方
✗ 错：用 max(三邻居)+1
✓ 对：必须用 min(三邻居)+1
max 会让一个长邻居就把正方形吹大，实际撑不齐——min 才保证三块都够长
✗ 错：只看左、上两个邻居
✓ 对：还要看左上角那个邻居
漏掉左上，L 形或缺角的区域会被误判成完整正方形
✗ 错：返回 best（边长）
✓ 对：返回 best * best（面积）
题目要的是面积，边长 3 的答案是 9 不是 3
✗ 错：matrix 里是字符 '1' 却按数字 1 比
✓ 对：比较 matrix[i][j] == '1'（带引号）
LeetCode 这题矩阵元素是字符 char，不是 int，写错恒不进分支、答案全 0
完整代码（Python / C++ / Java）
Python
class Solution:
def maximalSquare(self, matrix):
m, n = len(matrix), len(matrix[0])
# 多开一圈 0，省掉第一行/第一列的特判
dp = [[0]*(n+1) for _ in range(m+1)]
best = 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
best = max(best, dp[i][j])
return best * bestC++
class Solution {
public:
int maximalSquare(vector<vector<char>>& matrix) {
int m = matrix.size(), n = matrix[0].size(), best = 0;
// 多开一圈 0，下标整体右移一位
vector<vector<int>> dp(m + 1, vector<int>(n + 1, 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;
best = max(best, dp[i][j]);
}
}
}
return best * best;
}
};Java
class Solution {
public int maximalSquare(char[][] matrix) {
int m = matrix.length, n = matrix[0].length, best = 0;
// 多开一圈 0，下标整体右移一位
int[][] dp = new int[m + 1][n + 1];
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;
best = Math.max(best, dp[i][j]);
}
}
}
return best * best;
}
}套路模板 · 矩阵区域二维 DP（挖空骨架）
# 矩阵区域型二维 DP · 可背骨架
# ① 状态：dp[i][j] = 以 (i,j) 为右下角的某个量（边长/计数/最优）
# ② 边界：第一行、第一列就是地基（这里 = matrix 本身的值）
# ③ 转移：当前格满足条件时，由 上/左/左上 三个邻居推出
dp = [[0]*n for _ in range(m)]
for i in range(m):
for j in range(n):
if cell_ok(i, j): # ← 本题：matrix[i][j] == '1'
if i == 0 or j == 0:
dp[i][j] = base(i, j) # ← 本题：1
else:
dp[i][j] = combine(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])
# ← 本题 combine = min(...) + 1
ans = best(ans, dp[i][j]) # ← 本题：max；面积再平方// 矩阵区域型二维 DP · 可背骨架
vector<vector<int>> dp(m, vector<int>(n, 0));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (cellOk(i, j)) { // 本题: matrix[i][j]=='1'
if (i == 0 || j == 0)
dp[i][j] = base(i, j); // 本题: 1
else
dp[i][j] = combine(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
// 本题 combine = min(...) + 1
ans = best(ans, dp[i][j]); // 本题: max; 面积再平方
}
}
}// 矩阵区域型二维 DP · 可背骨架
int[][] dp = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (cellOk(i, j)) { // 本题: matrix[i][j]=='1'
if (i == 0 || j == 0)
dp[i][j] = base(i, j); // 本题: 1
else
dp[i][j] = combine(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
// 本题 combine = min(...) + 1
ans = best(ans, dp[i][j]); // 本题: max; 面积再平方
}
}
}复杂度
时间复杂度
O(m·n)
每个格子只填一次，填的时候查左/上/左上三个已算好的邻居，是 O(1)；总共 m×n 个格子
空间复杂度
O(m·n)
一张和矩阵同样大的 dp 表；因为只依赖上一行，可滚动压到 O(n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大正方形 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
dp 状态为什么定义成「以 (i,j) 为右下角」，而不是「左上角」或「包含 (i,j)」？+
定成右下角，转移就只依赖左、上、左上这三个已经算过的格子，天然符合从左上往右下的填表顺序；定成左上角则要依赖右、下方还没算的格子，反着来很别扭。
为什么是 min 不是 max？能用一句话证明吗？+
想以 (i,j) 为右下角撑出边长 k，必须左、上、左上同时都能撑 k−1，三块边长 k−1 的正方形才拼得满。只要有一块不够，就只能取到那块的尺寸——所以是三者取 最小再加 1。
能优化到 O(n) 空间吗？+
能。dp[i][j] 只用到当前行的左邻居、上一行的同列和上一行的左邻居，保留一行即可。用一维数组滚动，再拿一个变量缓存「左上角」那个会被覆盖掉的旧值，空间降到 O(n)。
如果问的是最大长方形面积（LeetCode 85）而不是正方形，这套还管用吗？+
不直接管用。长方形宽高可以不等，这个 min+1 的对称结构就失效了。85 题的主流解法是把每一行压成柱状图，再用单调栈求「柱状图中最大矩形」。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。