统计全为 1 的正方形子矩阵 图解题解
这道题到底在问什么
- 输入
- matrix = [[0,1,1,1],[1,1,1,1],[0,1,1,1]]
- 输出
- 15(包含 1x1、2x2、3x3)
- 输入
- matrix = [[1,0,1],[1,1,0],[1,1,0]]
- 输出
- 7
- 输入
- matrix = [[1]]
- 输出
- 1(单个 1)
最优解：一步一步想明白
- 3一句话套路:每个 1 格子看它正上方、正左方、左上方三个邻居,谁最小就卡住了能凑多大的正方形,取最小值加一。下面逐格填表。
- 4先看骨架:行头是行下标 r0 到 r2,列头是列下标 c0 到 c3。表里现在显示的是原始输入(0 或 1)。我们会从左上往右下,逐格把每个 1 改写成「以它为右下角的最大正方形边长」,同时累加答案。
- 5格子 (0,0) 本身是 0,没法当任何全 1 正方形的右下角,dp[0][0]=0,贡献 0。答案累计仍是 0。
- 6格子 (0,1) 是 1,但它在首行,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[0][1]=1,贡献 1。答案累计 = 1。
- 7格子 (0,2) 是 1,但它在首行,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[0][2]=1,贡献 1。答案累计 = 2。
- 8格子 (0,3) 是 1,但它在首行,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[0][3]=1,贡献 1。答案累计 = 3。
- 9格子 (1,0) 是 1,但它在首列,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[1][0]=1,贡献 1。答案累计 = 4。
- 10算 dp[1][1]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[0][1]=1,左方 dp[1][0]=1,左上 dp[0][0]=0。能凑出的正方形被这三个里最小的那个卡住。
- 11三者最小值是 0,加一得 dp[1][1]=1。这格作为右下角能凑出边长 1 到 1 的正方形,共 1 个,累加进答案。答案累计 = 5。
- 12算 dp[1][2]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[0][2]=1,左方 dp[1][1]=1,左上 dp[0][1]=1。能凑出的正方形被这三个里最小的那个卡住。
- 13三者最小值是 1,加一得 dp[1][2]=2。这格作为右下角能凑出边长 1 到 2 的正方形,共 2 个,累加进答案。答案累计 = 7。
- 14算 dp[1][3]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[0][3]=1,左方 dp[1][2]=2,左上 dp[0][2]=1。能凑出的正方形被这三个里最小的那个卡住。
- 15三者最小值是 1,加一得 dp[1][3]=2。这格作为右下角能凑出边长 1 到 2 的正方形,共 2 个,累加进答案。答案累计 = 9。
- 16格子 (2,0) 本身是 0,没法当任何全 1 正方形的右下角,dp[2][0]=0,贡献 0。答案累计仍是 9。
- 17算 dp[2][1]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[1][1]=1,左方 dp[2][0]=0,左上 dp[1][0]=1。能凑出的正方形被这三个里最小的那个卡住。
- 18三者最小值是 0,加一得 dp[2][1]=1。这格作为右下角能凑出边长 1 到 1 的正方形,共 1 个,累加进答案。答案累计 = 10。
- 19算 dp[2][2]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[1][2]=2,左方 dp[2][1]=1,左上 dp[1][1]=1。能凑出的正方形被这三个里最小的那个卡住。
- 20三者最小值是 1,加一得 dp[2][2]=2。这格作为右下角能凑出边长 1 到 2 的正方形,共 2 个,累加进答案。答案累计 = 12。
- 21算 dp[2][3]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[1][3]=2,左方 dp[2][2]=2,左上 dp[1][2]=2。能凑出的正方形被这三个里最小的那个卡住。
- 22三者最小值是 2,加一得 dp[2][3]=3。这格作为右下角能凑出边长 1 到 3 的正方形,共 3 个,累加进答案。答案累计 = 15。
- 23整张表填满了。每个格子里的数就是「以它为右下角的全 1 正方形个数」,把全表的 dp 值加起来 = 15,正是答案。绿格就是所有能当右下角的格子。
- 24复盘整条思路:dp[r][c] = 以 (r,c) 为右下角的最大全 1 正方形边长,也等于该格贡献的正方形个数;1 格取上、左、左上三者最小值加一,0 格记 0;逐格相加即总数 15。
⚠️ 容易写错的地方
✗ 错：把 dp 当成「正方形个数」直接累加邻居
✓ 对：dp 存的是边长,答案是把所有边长值相加
边长 dp[r][c] 时,边长 1 到 dp[r][c] 都成立,恰好 dp[r][c] 个,累加的就是边长
✗ 错：内部转移漏看左上,或首行首列越界
✓ 对：取上、左、左上三者最小值;r==0 或 c==0 时保持原值
漏看左上会漏掉对角线限制;首行首列做 r-1/c-1 会负下标越界
✗ 错：本格是 0 还去算 min
✓ 对：只有本格是 1 才转移,0 格固定为 0
0 格不可能当全 1 正方形的右下角,强行加一会凭空造出正方形
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
ans = 0
for r in range(m):
for c in range(n):
if matrix[r][c] and r and c:
matrix[r][c] = min(matrix[r-1][c], matrix[r][c-1], matrix[r-1][c-1]) + 1
ans += matrix[r][c]
return ansC++
#include <vector>
using namespace std;
class Solution {
public:
int countSquares(vector<vector<int>>& matrix) {
int m = matrix.size(), n = matrix[0].size(), ans = 0;
for (int r = 0; r < m; ++r) for (int c = 0; c < n; ++c) {
if (matrix[r][c] && r && c) matrix[r][c] = min({matrix[r-1][c], matrix[r][c-1], matrix[r-1][c-1]}) + 1;
ans += matrix[r][c];
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length, n = matrix[0].length, ans = 0;
for (int r = 0; r < m; r++) for (int c = 0; c < n; c++) {
if (matrix[r][c] == 1 && r > 0 && c > 0) matrix[r][c] = Math.min(matrix[r - 1][c], Math.min(matrix[r][c - 1], matrix[r - 1][c - 1])) + 1;
ans += matrix[r][c];
}
return ans;
}
}复杂度
时间
O(m·n)
每个格子只看三个已算好的邻居,常数次计算,遍历一遍矩阵
空间
O(1)
原地改写 matrix 当 dp 表,不额外开空间;若不许改输入则 O(m·n)
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 统计全为 1 的正方形子矩阵 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题和「最大正方形 lc221」有什么区别和联系?+
转移方程一模一样,都是 dp[r][c]=min(上,左,左上)+1。区别只在最后的统计:lc221 求最大全 1 正方形的面积,所以答案是 max(dp) 的平方;本题求所有全 1 正方形的个数,答案是 sum(dp)。理解了一道,另一道改一行统计即可。
如果不允许修改输入矩阵,怎么处理?+
另开一个同尺寸的 dp 数组即可,空间 O(m·n);或者只用滚动的两行(当前行和上一行),把空间压到 O(n)。因为转移只依赖上一行和当前行已算好的左侧,滚动数组完全够用。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 统计全为 1 的正方形子矩阵 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。