统计全为 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 再改写。

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 ans

C++

#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;
    }
}