统计全1正方形子矩阵的个数

题目描述

给定一个二维二进制矩阵（只包含0和1），请统计其中全由1组成的正方形子矩阵的个数。注意，正方形子矩阵的定义是：矩阵中一个连续的子区域，其行数和列数相等，且所有元素均为1。你需要统计所有可能的正方形子矩阵的个数，不同位置、不同大小的正方形分别计数。

例如，给定矩阵：

matrix = [
  [1, 0, 1],
  [1, 1, 0],
  [1, 1, 0]
]

其中全1正方形子矩阵有：

• 边长为1的：位置(0,0)、(0,2)、(1,0)、(1,1)、(2,0)、(2,1) 共6个。
• 边长为2的：以(1,0)为右下角的2x2子矩阵（包含(0,0)、(0,1)、(1,0)、(1,1)）是全部为1的正方形，这是1个。
  总数为7。

你的目标是设计一个时间复杂度尽可能低的算法，计算所有全1正方形子矩阵的个数。

解题思路

这是一道经典的线性动态规划问题，核心在于找到以每个位置 (i, j) 作为右下角时，能够构成的最大正方形的边长，并利用这个信息累加所有可能的正方形个数。

为什么以右下角为基准？因为动态规划通常按顺序（从上到下、从左到右）遍历矩阵，当我们到达 (i, j) 时，其左、上、左上的状态已经计算完毕，方便我们递推。

关键观察

设 dp[i][j] 表示以 (i, j) 作为右下角时，能够组成的全1正方形的最大边长。例如，dp[i][j] = 3 表示以 (i, j) 为右下角，存在一个 3x3 的全1正方形，且没有更大的全1正方形。

递推关系：

• 如果 matrix[i][j] == 0，显然 dp[i][j] = 0，因为右下角是0不可能构成全1正方形。
• 如果 matrix[i][j] == 1：
  • 考虑以 (i, j) 为右下角的正方形，其大小受限于：
    1. 以 (i-1, j) 为右下角的最大正方形边长（上方）
    2. 以 (i, j-1) 为右下角的最大正方形边长（左方）
    3. 以 (i-1, j-1) 为右下角的最大正方形边长（左上方）
  • 因为要构成更大的正方形，其上方、左方、左上方的区域也必须能构成足够大的正方形。因此，最大边长是这三者的最小值再加1。
  • 递推式：dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

为什么最小值？
想象一个 3x3 的全1正方形，其右下角为 (i, j)，那么其上方必须有一个至少 2x2 的全1正方形（以 (i-1, j) 为右下角），左方和左上方同理。如果其中任何一个方向能构成的最大边长较小，整体就会被限制。取最小值保证了所有方向都满足条件。

统计个数：

• 如果 dp[i][j] = k，表示以 (i, j) 为右下角，可以构成边长为 1, 2, ..., k 的正方形各一个。因此，dp[i][j] 的值直接贡献了 k 个正方形。
• 最终答案：sum(dp[i][j] for all i, j)

详细步骤

假设矩阵有 m 行、n 列。

1. 初始化

   • 创建一个二维数组 dp，大小与矩阵相同，初始化为0。
   • 为了处理边界情况（第一行、第一列），可以在 dp 外围加一圈0，或者单独处理。

2. 遍历矩阵（从左上到右下）

   • 对于每个位置 (i, j)：
     • 如果 matrix[i][j] == 0，则 dp[i][j] = 0。
     • 如果 matrix[i][j] == 1：
       • 如果 i == 0 或 j == 0（即第一行或第一列），最大边长只能是1，因为没有足够的相邻位置构成更大的正方形，所以 dp[i][j] = 1。
       • 否则，dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

3. 累加结果

   • 遍历 dp 数组，将每个值累加到结果 count 中。

4. 返回结果

   • 返回 count。

举例说明

以题目示例矩阵：

matrix = [
  [1, 0, 1],
  [1, 1, 0],
  [1, 1, 0]
]

计算过程如下（dp 值表示以该位置为右下角的最大正方形边长）：

初始 dp 全0。

i=0（第一行）：

• (0,0): matrix=1 → 第一行 → dp=1
• (0,1): matrix=0 → dp=0
• (0,2): matrix=1 → 第一行 → dp=1

i=1：

• (1,0): matrix=1 → 第一列 → dp=1
• (1,1): matrix=1 → min(dp[0,1]=0, dp[1,0]=1, dp[0,0]=1) + 1 = 0+1=1
• (1,2): matrix=0 → dp=0

i=2：

• (2,0): matrix=1 → 第一列 → dp=1
• (2,1): matrix=1 → min(dp[1,1]=1, dp[2,0]=1, dp[1,0]=1) + 1 = 1+1=2
• (2,2): matrix=0 → dp=0

得到 dp 数组：

[1, 0, 1]
[1, 1, 0]
[1, 2, 0]

累加所有值：1+0+1 + 1+1+0 + 1+2+0 = 7，即为答案。

复杂度分析

• 时间复杂度：O(m*n)，遍历一次矩阵。
• 空间复杂度：O(m*n)，用于存储 dp 数组。可优化为 O(n) 只保留上一行和当前行，但为了清晰，这里用二维数组。

核心要点

• 定义 dp[i][j] 为以 (i, j) 为右下角的最大全1正方形边长。
• 递推式基于左、上、左上三个方向的最小值。
• 累加每个 dp[i][j] 即可得到总正方形数，因为边长 k 包含了所有更小的正方形。

这种方法高效地避免了暴力枚举所有可能正方形（O(m²n²) 复杂度），是典型的动态规划空间换时间。