题目描述
思路解析
一句话答案：LeetCode 1277 统计全为 1 的正方形子矩阵：dp[i][j]=以 (i,j) 为右下角的最大正方形边长=min(上、左、左上)+1；边长值即该格贡献的正方形个数，全表求和即答案。O(m·n) 时间、O(1) 空间。
统计全 1 正方形，连 1x1 都要数吗
给一张只含 0 和 1 的矩阵，数出所有全是 1 的正方形子矩阵有多少个。边长 1、2x2、3x3 都算，只要盖住的格子全是 1 就计一个。以 matrix=[[0,1,1,1],[1,1,1,1],[0,1,1,1]] 为例，这是一张 m 行 n 列的矩阵（m=3、n=4），答案 15，要的是总个数。矩阵里用 (r,c) 指第 r 行第 c 列，行列号都从 0 数起。
边长最大 min(m,n)，逐尺寸验为什么算不过账
一张 m×n 矩阵里，边长 k 的正方形有 (m-k+1)(n-k+1) 个，k 从 1 试到 min(m,n)。逐个摆出来验证是不是全 1，哪怕验大一号时只补看新添的一行一列、不整块重扫，总成本也到 O(m·n·min(m,n)²) 量级——大 O 记号描述矩阵变大时计算量怎么涨。
每格记一个数，为什么全表一加就是答案
与其枚举正方形，不如给每格记一个数。定义 dp[r][c] 为「以 (r,c) 为右下角能凑出的最大全 1 正方形边长」，这个「把局部结果存下、后面直接取用不重算」的数就是动态规划里的状态。它还藏第二层意思：以 (r,c) 收尾、边长 1 到 dp[r][c] 的正方形各一个，恰好贡献 dp[r][c] 个，全表相加就是总数。0 格当不了右下角，dp 记 0。
凭什么取上、左、左上三者最小再加一
一个是 1 的格子想当边长 k 正方形的右下角，正上、正左、左上必须都已能撑出边长至少 k-1 的正方形，少一个都塌。所以 dp[r][c]=min(dp[r-1][c], dp[r][c-1], dp[r-1][c-1])+1，这条由三个邻居推出本格的式子就是转移式（由已算好的格子推出当前格）。谁最小就卡死本格能撑多大。首行首列的 1 没有左上空间，只能记 1。
拿示例 15 那张表逐格填一遍
从左上往右下逐格填。首行首列的 1 各记 1，答案累到 4。dp[1][1] 三邻居上 1、左 1、左上 0，取最小 0 加一得 1；同理 dp[1][2] 上 1、左 1、左上 1 得 2、dp[1][3] 上 1、左 2、左上 1 得 2。(2,0) 是 0 记 0；dp[2][1] 得 1；dp[2][2] 上 2、左 1、左上 1 得 2；dp[2][3] 三邻居都是 2 得 3。全表十二格 0、1、1、1、1、1、2、2、0、1、2、3 相加正好 15。
累加时每个 1 只记 1，答案为什么会缩水
把 ans 写成「每见一个 1 就加 1」是最常见的写错：只数了 1x1，嵌在里面的 2x2、3x3 全漏了，示例从 15 缩成 10（即 1 的个数），累加的必须是 dp 值即边长本身。每格只看三个已算好的邻居，遍历一遍 O(m·n) 时间；原地改 matrix 当 dp 表，额外空间 O(1)（不许改输入则另开表 O(m·n)）。边界：全 0 矩阵答案 0，单格 [[1]] 是 1；0 格必须钉死为 0、不参与 min 加一，先判 matrix[r][c] 为 1 且 r、c 大于 0 再改写。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
一句话套路:每个 1 格子看它正上方、正左方、左上方三个邻居,谁最小就卡住了能凑多大的正方形,取最小值加一。下面逐格填表。
先看骨架:行头是行下标 r0 到 r2,列头是列下标 c0 到 c3。表里现在显示的是原始输入(0 或 1)。我们会从左上往右下,逐格把每个 1 改写成「以它为右下角的最大正方形边长」,同时累加答案。
格子 (0,0) 本身是 0,没法当任何全 1 正方形的右下角,dp[0][0]=0,贡献 0。答案累计仍是 0。
格子 (0,1) 是 1,但它在首行,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[0][1]=1,贡献 1。答案累计 = 1。
格子 (0,2) 是 1,但它在首行,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[0][2]=1,贡献 1。答案累计 = 2。
格子 (0,3) 是 1,但它在首行,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[0][3]=1,贡献 1。答案累计 = 3。
格子 (1,0) 是 1,但它在首列,上方或左侧没有空间,最大只能凑出 1x1 正方形,dp[1][0]=1,贡献 1。答案累计 = 4。
算 dp[1][1]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[0][1]=1,左方 dp[1][0]=1,左上 dp[0][0]=0。能凑出的正方形被这三个里最小的那个卡住。
三者最小值是 0,加一得 dp[1][1]=1。这格作为右下角能凑出边长 1 到 1 的正方形,共 1 个,累加进答案。答案累计 = 5。
算 dp[1][2]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[0][2]=1,左方 dp[1][1]=1,左上 dp[0][1]=1。能凑出的正方形被这三个里最小的那个卡住。
三者最小值是 1,加一得 dp[1][2]=2。这格作为右下角能凑出边长 1 到 2 的正方形,共 2 个,累加进答案。答案累计 = 7。
算 dp[1][3]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[0][3]=1,左方 dp[1][2]=2,左上 dp[0][2]=1。能凑出的正方形被这三个里最小的那个卡住。
三者最小值是 1,加一得 dp[1][3]=2。这格作为右下角能凑出边长 1 到 2 的正方形,共 2 个,累加进答案。答案累计 = 9。
格子 (2,0) 本身是 0,没法当任何全 1 正方形的右下角,dp[2][0]=0,贡献 0。答案累计仍是 9。
算 dp[2][1]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[1][1]=1,左方 dp[2][0]=0,左上 dp[1][0]=1。能凑出的正方形被这三个里最小的那个卡住。
三者最小值是 0,加一得 dp[2][1]=1。这格作为右下角能凑出边长 1 到 1 的正方形,共 1 个,累加进答案。答案累计 = 10。
算 dp[2][2]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[1][2]=2,左方 dp[2][1]=1,左上 dp[1][1]=1。能凑出的正方形被这三个里最小的那个卡住。
三者最小值是 1,加一得 dp[2][2]=2。这格作为右下角能凑出边长 1 到 2 的正方形,共 2 个,累加进答案。答案累计 = 12。
算 dp[2][3]:本格是 1,点亮它的三个邻居(蓝格)。上方 dp[1][3]=2,左方 dp[2][2]=2,左上 dp[1][2]=2。能凑出的正方形被这三个里最小的那个卡住。
三者最小值是 2,加一得 dp[2][3]=3。这格作为右下角能凑出边长 1 到 3 的正方形,共 3 个,累加进答案。答案累计 = 15。
整张表填满了。每个格子里的数就是「以它为右下角的全 1 正方形个数」,把全表的 dp 值加起来 = 15,正是答案。绿格就是所有能当右下角的格子。
复盘整条思路:dp[r][c] = 以 (r,c) 为右下角的最大全 1 正方形边长,也等于该格贡献的正方形个数;1 格取上、左、左上三者最小值加一,0 格记 0;逐格相加即总数 15。
边界:单格按本值;全 0 答案 0;2x2 全 1 答案 5,各尺寸都要数到。
两个追问:和 lc221 同转移,差在 max 平方还是 sum;不许改输入就另开 dp 或滚动两行。
参考代码
from typing import Listclass 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 ans复杂度
- 时间：O(m·n)，每个格子只看三个已算好的邻居,常数次计算,遍历一遍矩阵
- 空间：O(1)，原地改写 matrix 当 dp 表,不额外开空间;若不许改输入则 O(m·n)
易错点
面试追问把动画讲成自己的话
追问这题和「最大正方形 lc221」有什么区别和联系?
追问如果不允许修改输入矩阵,怎么处理?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。再去主线里挑下一道练手。
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题