1. 题目解析与核心思路这道题目要求统计一个由0和1组成的二维矩阵中全部由1构成的正方形子矩阵的数量。看似简单但直接暴力枚举所有可能的正方形子矩阵并检查其元素是否为1时间复杂度会非常高O(n^3)对于较大的矩阵显然不够高效。1.1 动态规划解法经过分析我们可以采用动态规划(DP)来解决这个问题。定义dp[i][j]表示以(i,j)为右下角的正方形子矩阵的最大边长。那么dp[i][j]的值取决于其上方、左方和左上方的dp值如果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,j)为右下角的正方形子矩阵的最大边长取决于它周围三个方向能构成的正方形的最小值再加上当前这个1。1.2 为什么这样设计DP这种设计之所以有效是因为正方形的性质决定了它需要四个角都满足条件右下角的边长受限于其他三个方向的限制取最小值保证了所有方向都能满足条件2. 详细实现步骤2.1 初始化DP数组首先创建一个与原矩阵大小相同的dp数组初始化第一行和第一列dp[0][j] matrix[0][j] (第一行)dp[i][0] matrix[i][0] (第一列)因为这些位置无法形成更大的正方形所以最大边长就是它们本身的值(0或1)。2.2 填充DP数组从(1,1)开始遍历矩阵按照状态转移方程填充dp数组for i in range(1, rows): for j in range(1, cols): if matrix[i][j] 1: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 12.3 统计结果最终的答案就是dp数组中所有值的总和因为dp[i][j]不仅表示最大边长还表示以(i,j)为右下角的所有可能正方形子矩阵的数量。3. 完整代码实现def countSquares(matrix): if not matrix: return 0 rows len(matrix) cols len(matrix[0]) dp [[0]*cols for _ in range(rows)] total 0 # 初始化第一行和第一列 for i in range(rows): dp[i][0] matrix[i][0] total dp[i][0] for j in range(1, cols): dp[0][j] matrix[0][j] total dp[0][j] # 填充DP数组 for i in range(1, rows): for j in range(1, cols): if matrix[i][j] 1: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1 total dp[i][j] return total4. 复杂度分析时间复杂度O(mn)需要遍历整个矩阵一次空间复杂度O(mn)需要额外的dp数组存储中间结果5. 优化空间复杂度实际上我们可以优化空间复杂度到O(n)因为每次计算dp[i][j]只需要当前行和上一行的数据def countSquares(matrix): if not matrix: return 0 rows len(matrix) cols len(matrix[0]) dp [0] * cols total 0 # 处理第一行 for j in range(cols): dp[j] matrix[0][j] total dp[j] # 处理剩余行 for i in range(1, rows): new_dp [0] * cols new_dp[0] matrix[i][0] total new_dp[0] for j in range(1, cols): if matrix[i][j] 1: new_dp[j] min(dp[j], new_dp[j-1], dp[j-1]) 1 total new_dp[j] dp new_dp return total6. 常见错误与调试技巧6.1 边界条件处理容易忽略矩阵为空或只有一行/一列的情况。务必先检查这些边界条件。6.2 初始化错误第一行和第一列的初始化需要单独处理不能直接套用状态转移方程。6.3 索引越界在实现时要注意数组索引的范围特别是在处理第一行和第一列时。7. 实际应用场景这种统计子矩阵的技术在实际中有广泛应用图像处理中寻找特定图案计算机视觉中的物体检测地理信息系统中的区域分析游戏开发中的碰撞检测8. 类似题目推荐Maximal Square - 找出只包含1的最大正方形面积Maximal Rectangle - 找出只包含1的最大矩形面积Count Submatrices With All Ones - 统计所有全1子矩阵(不限于正方形)9. 个人解题心得在实际解题过程中我发现画图辅助理解状态转移方程非常有效先考虑暴力解法再思考如何优化是很好的解题策略动态规划问题的关键是找到正确的状态定义和转移方程空间优化虽然重要但初期可以先实现基本解法确保正确性后再优化