---

1277. 统计全为 1 的正方形子矩阵

• 标签：数组、动态规划、矩阵
• 难度：中等

题目链接

• 1277. 统计全为 1 的正方形子矩阵 - 力扣

题目大意

描述：给你一个 $m \times n$ 的矩阵，矩阵中的元素不是 $0$ 就是 $1$。

要求：统计并返回其中完全由 $1$ 组成的正方形子矩阵的个数。

说明：

• $1 \le arr.length \le 300$。
• $1 \le arr[0].length \le 300$。
• $0 \le arr[i][j] \le 1$。

示例：

• 示例 1：

输入：matrix =
[
  [0,1,1,1],
  [1,1,1,1],
  [0,1,1,1]
]
输出：15
解释： 
边长为 1 的正方形有 10 个。
边长为 2 的正方形有 4 个。
边长为 3 的正方形有 1 个。
正方形的总数 = 10 + 4 + 1 = 15.

• 示例 2：

输入：matrix = 
[
  [1,0,1],
  [1,1,0],
  [1,1,0]
]
输出：7
解释：
边长为 1 的正方形有 6 个。 
边长为 2 的正方形有 1 个。
正方形的总数 = 6 + 1 = 7.

解题思路

思路 1：动态规划

1. 阶段划分

按照矩阵中每个位置 $(i, j)$ 作为正方形的右下角来划分阶段。对于每个位置，我们计算以它为右下角能构成的全 $1$ 正方形的最大边长。

2. 定义状态

定义 $dp[i][j]$ 表示以 $(i, j)$ 为右下角的最大全 $1$ 正方形的边长。

3. 状态转移方程

当 $matrix[i][j] == 1$ 时，以 $(i, j)$ 为右下角的正方形能有多大，取决于它的三个邻居：

• 左边 $(i, j-1)$ 能提供的最大边长
• 上边 $(i-1, j)$ 能提供的最大边长
• 左上角 $(i-1, j-1)$ 能提供的最大边长

这三者中的最小值决定了短板，再加上当前格子自身的 $1$，就是当前位置能形成的最大正方形边长：

$$dp[i][j] = \min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1$$

如果 $matrix[i][j] == 0$，则 $dp[i][j] = 0$。

为什么取最小值？可以想象一下，要形成一个 $k \times k$ 的全 $1$ 正方形，它的右上、左下、右下三个「角」区域都必须至少是 $(k-1) \times (k-1)$ 的全 $1$ 正方形。三个方向中任何一个「不够高」，都会限制最终的大小。

4. 初始条件

第一行（$i = 0$）和第一列（$j = 0$）的位置，最大边长只能是 $matrix[i][j]$ 本身（$0$ 或 $1$）。

5. 最终结果

$dp[i][j] = k$ 意味着以 $(i, j)$ 为右下角，可以形成边长分别为 $1, 2, ..., k$ 的正方形。所以每个 $dp[i][j]$ 贡献了 $k$ 个正方形。把所有 $dp[i][j]$ 加起来就是答案。

结合示例 1 走一遍：

矩阵：

0 1 1 1
1 1 1 1
0 1 1 1

计算 $dp$ 数组：

• 第一行：$[0, 1, 1, 1]$
• $(1,0)$：$matrix=1$，第一列 → $dp=1$
• $(1,1)$：$matrix=1$，$\min(dp[0][1], dp[1][0], dp[0][0]) + 1 = \min(1,1,0) + 1 = 1$
• $(1,2)$：$matrix=1$，$\min(1,1,1) + 1 = 2$
• $(1,3)$：$matrix=1$，$\min(1,2,1) + 1 = 2$
• $(2,0)$：第一列 → $dp = 0$
• $(2,1)$：$\min(dp[1][1], dp[2][0], dp[1][0]) + 1 = \min(1,0,1) + 1 = 1$
• $(2,2)$：$\min(2,1,1) + 1 = 2$
• $(2,3)$：$\min(2,2,2) + 1 = 3$

$dp$ 数组：

0 1 1 1
1 1 2 2
0 1 2 3

总和 $= 0+1+1+1+1+1+2+2+0+1+2+3 = 15$，与题目一致。

思路 1：代码

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        m, n = len(matrix), len(matrix[0])
        # dp 数组，dp[i][j] 表示以 (i,j) 为右下角的最大正方形边长
        dp = [[0] * n for _ in range(m)]
        ans = 0

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 1:
                    if i == 0 or j == 0:
                        # 边界位置，最大边长就是自身
                        dp[i][j] = 1
                    else:
                        # 取三个邻居的最小值 + 1
                        dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
                    # dp[i][j] 的值就是以 (i,j) 为右下角的正方形个数
                    ans += dp[i][j]

        return ans

思路 1：复杂度分析

• 时间复杂度：$O(m \times n)$，需要遍历整个矩阵一次，每个位置进行常数时间的计算。
• 空间复杂度：$O(m \times n)$，需要一个与原始矩阵尺寸相同的 $dp$ 数组。可以优化为 $O(n)$（只保留当前行和上一行），但 $m, n \le 300$ 时完全不需要。