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

考点

• 子矩形DP

思路

---

一、问题描述

给定一个仅由 0 和 1 组成的二维矩阵 matrix，要求统计其中所有元素均为 1 的正方形子矩阵的个数。

• 子矩阵必须是正方形
• 子矩阵中所有元素必须为 1
• 不限制正方形的边长

---

二、核心建模思想

关键观察

如果我们以某个位置 (i, j) 作为右下角：

• 若该位置是 0，显然无法构成任何全 1 正方形；
• 若该位置是 1，则：
  • 至少可以构成一个 1 × 1 的正方形；
  • 是否能扩展为更大的正方形，取决于它的上方、左方、左上方。

因此，自然的建模方式是：

关注：以 (i, j) 为右下角，最多能形成多大的全 1 正方形。

---

三、状态定义

设二维 DP 数组 f，定义为： \[ f[i][j] = \text{以 } (i, j) \text{ 为右下角的全 1 正方形的最大边长} \] 说明：

• (i, j) 采用 1-based 下标，方便处理边界；
• f[i][j] = 0 表示无法形成任何正方形。

---

四、状态转移方程

1. 基本情况

若原矩阵中： \[ matrix[i-1][j-1] = 0 \] 则： \[ f[i][j] = 0 \] 因为右下角为 0，任何正方形都不可能成立。

---

2. 递推关系（核心）

若： \[ matrix[i-1][j-1] = 1 \] 那么要想形成边长大于 1 的正方形，必须满足：

• 上方 (i-1, j) 至少能形成边长为 \(x\) 的正方形；
• 左方 (i, j-1) 至少能形成边长为 \(x\) 的正方形；
• 左上 (i-1, j-1) 至少能形成边长为 \(x\) 的正方形。

因此，最大可扩展的边长由这三者的最小值决定： \[ f[i][j] = 1 + \min \big( f[i-1][j],\; f[i][j-1],\; f[i-1][j-1] \big) \]

---

五、为什么“最大边长之和”就是答案？

这是本题最关键、也最容易被误解的一点。

结论

若： \[ f[i][j] = L \] 则意味着：

• 以 (i, j) 为右下角：
  • 存在 1 × 1 的全 1 正方形；
  • 存在 2 × 2 的全 1 正方形；
  • …
  • 存在 L × L 的全 1 正方形。

因此，该位置一共贡献 L 个正方形。

---

总答案

将所有位置的贡献累加： \[ \text{ans} = \sum_{i=1}^{n} \sum_{j=1}^{m} f[i][j] \]

---

六、算法复杂度分析

• 时间复杂度： \[ O(n \times m) \]

• 空间复杂度： \[ O(n \times m) \] （可进一步压缩为一维 DP，但不影响建模本质）

---

七、参考实现（附完整注释）

class Solution {
 public:
  int countSquares(vector<vector<int>>& matrix) {
    int n = matrix.size();
    int m = matrix[0].size();

    // f[i][j]：以 (i, j) 为右下角的全 1 正方形的最大边长
    // 使用 1-based 下标，避免边界判断
    vector<vector<int>> f(n + 1, vector<int>(m + 1, 0));

    int ans = 0;

    for (int i = 1; i <= n; ++i) {
      for (int j = 1; j <= m; ++j) {
        // 若当前位置为 0，无法形成正方形
        if (matrix[i - 1][j - 1] == 0) continue;

        // 状态转移：
        // 当前最大边长 = 1 + min(上, 左, 左上)
        f[i][j] = 1 + min(
            f[i - 1][j],
            min(f[i][j - 1], f[i - 1][j - 1])
        );

        // 累加贡献
        ans += f[i][j];
      }
    }

    return ans;
  }
};