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

整体思路

这段代码旨在解决一个经典的二维矩阵问题：统计全为 1 的正方形子矩阵个数 (Count Square Submatrices with All Ones)。问题要求计算在一个由 0 和 1 组成的矩阵中，所有元素都为 1 的正方形子矩阵的总数量。

该算法采用了一种非常高效的 动态规划 (Dynamic Programming) 方法。其核心思想是构建一个 DP 表，并利用子问题的解来推导当前问题的解。

1. 状态定义 (DP State)：

   • 算法创建了一个 dp 数组，其大小比原矩阵 matrix 大一圈（[m+1][n+1]），这种“填充”技巧可以简化边界条件的处理。
   • dp[i][j] 的核心含义是：以 matrix[i-1][j-1] 为右下角 的、全由 1 组成的最大正方形的 边长。

2. 状态转移方程：

   • 算法遍历原矩阵 matrix 的每一个单元格 (i, j)。
   • 只有当 matrix[i][j] 本身为 1 时，它才有可能成为某个正方形的右下角。
   • 如果 matrix[i][j] == 1，那么以它为右下角的最大正方形的边长，取决于其 上方、左方 和 左上方 三个相邻位置所能形成的最大正方形。
   • 具体来说，一个新的、更大的 k x k 正方形，必须依赖于它旁边已经存在三个 (k-1) x (k-1) 的正方形。因此，新的边长受限于这三者中的最小值。
   • 状态转移方程为：
     dp[i+1][j+1] = min(dp[i][j+1], dp[i+1][j], dp[i][j]) + 1
     （这里的 dp 索引都比 matrix 的索引大 1）。

3. 核心计数逻辑：

   • 这是该算法最巧妙的一点。dp[i+1][j+1] 的值，比如说 k，不仅代表以 matrix[i][j] 为右下角的最大正方形边长是 k，它还隐含了以该点为右下角的、边长为 k-1, k-2, …, 1 的正方形也必然存在。
   • 因此，dp[i+1][j+1] 的值 k，恰好等于以 matrix[i][j] 为右下角的所有正方形的总数。
   • 所以，在计算出每个 dp[i+1][j+1] 的值之后，直接将其累加到最终结果 ans 中，就可以统计出矩阵中所有的正方形。

4. 算法流程：

   • 创建一个 dp 表。
   • 遍历输入矩阵 matrix。
   • 如果 matrix[i][j] 是 1，则根据状态转移方程计算 dp[i+1][j+1] 的值。
   • 将计算出的 dp[i+1][j+1] 累加到 ans。
   • 如果 matrix[i][j] 是 0，则 dp[i+1][j+1] 保持默认值 0，对 ans 没有贡献，这符合逻辑。
   • 遍历结束后返回 ans。

完整代码

class Solution {/*** 统计一个二维矩阵中，所有元素都为 1 的正方形子矩阵的总数量。* @param matrix 一个由 0 和 1 组成的二维整数数组* @return 全为 1 的正方形子矩阵的总数*/public int countSquares(int[][] matrix) {int m = matrix.length;int n = matrix[0].length;// dp 表：dp[i][j] 表示以 matrix[i-1][j-1] 为右下角的最大正方形的边长。// 使用 m+1 和 n+1 的大小是为了增加一圈“哨兵”0，简化边界条件的处理。int[][] dp = new int[m + 1][n + 1];// ans: 用于累计正方形的总数。int ans = 0;// 遍历原始矩阵的每一个单元格for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {// 只有当当前单元格为 1 时，它才可能成为正方形的一部分if (matrix[i][j] == 1) {// 状态转移方程：// 以 (i, j) 为右下角的最大正方形的边长，取决于其左、上、左上三个方向// 形成的最大正方形边长中的最小值，然后再加上当前这个单元格（+1）。// dp[i+1][j+1] 对应 matrix[i][j]。dp[i + 1][j + 1] = Math.min(Math.min(dp[i][j + 1], dp[i + 1][j]), dp[i][j]) + 1;// 核心计数逻辑：// dp[i+1][j+1] 的值 k，代表以 (i, j) 为右下角的正方形有 k 个// (边长分别为 1, 2, ..., k)。// 因此，直接将这个值累加到总数中。ans += dp[i + 1][j + 1];}}}// 返回最终统计的结果return ans;}
}

时空复杂度

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

1. 循环：算法的核心是两个嵌套的 for 循环，它们完整地遍历了输入矩阵 matrix 的每一个单元格。
   • 外层循环执行 m 次（m 是矩阵的行数）。
   • 内层循环执行 n 次（n 是矩阵的列数）。
2. 循环内部操作：
   • 在循环的每一次迭代中，执行的操作（if 判断、Math.min、数组读写、加法）都是常数时间复杂度的，即 O(1)。

综合分析：
算法的总时间复杂度是 m * n 次 O(1) 操作，因此最终的时间复杂度为 O(m * n)。

空间复杂度：O(m * n)

1. 主要存储开销：算法创建了一个名为 dp 的二维数组来存储动态规划的状态。
2. 空间大小：dp 数组的维度是 (m + 1) x (n + 1)。其占用的空间与输入矩阵的大小 m * n 成正比。
3. 其他变量：m, n, ans, i, j 等变量都只占用常数级别的空间。

综合分析：
算法所需的额外辅助空间主要由 dp 数组决定。因此，其空间复杂度为 O(m * n)。

参考灵神