题目

给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 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 <= arr.length <= 300
1 <= arr[0].length <= 300
0 <= arr[i][j] <= 1

解题思路

解决这类涉及子问题重叠的矩阵问题，暴力解法（遍历所有可能的正方形左上角和边长）的时间复杂度会非常高，而动态规划可以通过记录子问题的解来避免重复计算。

我们的核心思路是：对于矩阵中的每一个点 (i, j)，我们试图计算出以这个点为右下角的最大全 1 正方形的边长。

1.状态定义

这是动态规划最关键的一步。我们创建一个和原矩阵 matrix 大小相同的 dp 矩阵。

dp[i][j] 的含义是：以 matrix[i][j] 为右下角的全 1 正方形的最大边长。

理解这个定义是解题的关键。

如果 matrix[i][j] 是 0，那么任何以它为右下角的正方形都不可能存在，所以 dp[i][j] 必然为 0。
如果 matrix[i][j] 是 1，那么 dp[i][j] 的值将取决于它周围的邻居。

2.状态转移方程

这是动态规划的核心，即如何根据已知的子问题解来推导出当前问题的解。

假设我们要计算 dp[i][j]，并且已知 matrix[i][j] == 1。

想象一下，如果一个以 (i, j) 为右下角的正方形边长为 k (k > 1)，那么它必然包含以下三个部分：

一个以 (i-1, j) 为右下角的，边长至少为 k-1 的正方形。
一个以 (i, j-1) 为右下角的，边长至少为 k-1 的正方形。
一个以 (i-1, j-1) 为右下角的，边长至少为 k-1 的正方形。

这三个区域必须也都是全 1。如下图所示：

     j-1  j
      |   |
i-1 - A | B
      --+--
i   - C | D  <-- (i, j) is D

要让 D 成为一个边长为 k 的正方形的右下角，那么 A, B, C 三个点为右下角的正方形边长都必须不小于 k-1。

所以，D 能构成的最大正方形的边长，受限于它左边、上边、左上三个方向能构成的最大正方形的边长。具体来说，它取决于这三者中的最小值。

因此，我们得到了状态转移方程：

如果 matrix[i][j] == 0，则 dp[i][j] = 0。
如果 matrix[i][j] == 1，则 dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1。

边界条件： 对于第一行 (i=0) 和第一列 (j=0) 的元素，它们没有左边或者上边的元素。如果 matrix[i][j] == 1，它们自身就能构成一个边长为 1 的正方形。所以：

dp[0][j] = matrix[0][j]
dp[i][0] = matrix[i][0]

3.计算总数

我们已经知道 dp[i][j] 代表以 (i, j) 为右下角的最大正方形边长。这个值有什么用呢？

一个关键的发现是：如果 dp[i][j] = k，这表明以 (i, j) 为右下角，存在一个边长为 k 的大正方形。同时，这也意味着以它为右下角，也必然存在边长为 k-1, k-2, ..., 1 的正方形。

例如，如果 dp[i][j] = 3，说明这里有一个 3x3 的正方形，那么也一定有一个 2x2 和一个 1x1 的正方形（它们都嵌套在 3x3 的正方形内部，且共享同一个右下角）。

所以，dp[i][j] 的值 k，恰好代表了以 (i, j) 为右下角的正方形的总个数。

因此，我们只需要将 dp 矩阵中所有元素的值求和，就能得到整个矩阵中正方形的总数。

总数 = ∑ dp[i][j] (对所有 i, j)

实现思路

创建一个与 matrix 等大的 dp 矩阵，以及一个计数器 count 初始化为 0。
遍历 matrix 的每一个元素 matrix[i][j]。
处理边界（第一行和第一列）：
- 如果 i=0 或 j=0，则 dp[i][j] = matrix[i][j]。
处理非边界元素：
- 如果 matrix[i][j] == 1，则 dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1。
- 如果 matrix[i][j] == 0，则 dp[i][j] = 0。（这一步可以省略，因为 dp 矩阵默认初始化为 0）
在计算出每一个 dp[i][j] 后，立即将它的值累加到 count 中：count += dp[i][j]。
遍历结束后，返回 count。

具体代码

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {

        int m = matrix.size();
        int n = matrix[0].size();
        vector<vector<int>> dp(m, vector<int>(n, 0)); // 建立dp数组
        int result = 0;

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                int current = matrix[i][j];
                if(i == 0 || j == 0) // 在边缘的右下角大小只可能为1
                    dp[i][j] = current;
                else // 一般情况的右下角处理
                {
                    if(matrix[i][j])
                    // 如果当前位置不是0
                        dp[i][j] = min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]}) + 1;
                    else
                        dp[i][j] = 0;
                }
                result += dp[i][j];
            }
        }
        return result;
    }
};

改进思路

状态转移方程： dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1

当计算 matrix[i][j] (即 dp[i][j]) 的值时，你需要的只是它左边 (matrix[i][j-1])、上边 (matrix[i-1][j]) 和左上角 (matrix[i-1][j-1]) 的 dp 值。

由于遍历顺序是从上到下、从左到右，当计算到 (i, j) 时：

matrix[i-1][j] 已经被计算并更新为最终的 dp 值了。
matrix[i][j-1] 已经被计算并更新为最终的 dp 值了。
matrix[i-1][j-1] 已经被计算并更新为最终的 dp 值了。

计算 (i, j) 所需的所有依赖项都已经是计算完成的 dp 值，而不是原始的 0 或 1。而且，一旦 matrix[i][j] 计算完毕，原始的 matrix[i][j] 的值（那个 0 或 1）对于后续的计算就再也没有用处了。

所以可以在直接在输入的 matrix 上进行计算和修改，用 matrix 本身来存储 dp 状态值，同时也可以舍去很多状态检测。

改进后代码

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {

        int m = matrix.size();
        int n = matrix[0].size();
        int result = 0;
        // 不用新建数组，在原数组上计算即可

        for(int i = 0; i < m; i++)
        {
            for(int j = 0; j < n; j++)
            {
                if(i && j) // 只关心非左上边缘部分
                {
                    if(matrix[i][j] & 1) // 这个位置是1
                        matrix[i][j] = min({matrix[i - 1][j], matrix[i][j - 1], matrix[i - 1][j - 1]}) + 1;  
                }
                result += matrix[i][j];
            }
        }
        return result;
    }
};

复杂度分析

时间复杂度: O(m * n)

原因: 代码核心是两个嵌套的 for 循环，外层循环 m 次（行数），内层循环 n 次（列数）。循环体内部的操作（取最小值、加法等）都是常数时间。因此，总的执行时间与矩阵的元素总数 (m * n) 成正比。

空间复杂度: O(1)

原因: 没有创建任何新的数组或矩阵来存储中间结果。而是直接在输入的 matrix 数组上进行修改。算法运行过程中，只使用了像 m, n, result, i, j 这样有限几个变量，它们占用的空间是固定的，不会随着矩阵变大而变大。因此，额外空间复杂度是常数级的。

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

beautifulremi

题目