1. 问题背景与理解今天我们来深入探讨LeetCode第1277题统计全为1的正方形子矩阵。这是一道经典的动态规划问题在2023年LeetCode周赛430中出现过也是热门100题中的常客。题目要求给定一个由0和1组成的二维矩阵统计其中全部由1组成的正方形子矩阵的数量。举个例子对于矩阵[ [0,1,1,1], [1,1,1,1], [0,1,1,1] ]正确输出应该是15因为存在15个全1的正方形子矩阵。这个问题看似简单但要想出最优解法需要一定的技巧。2. 暴力解法分析2.1 直观思路最直观的解法是暴力枚举所有可能的正方形子矩阵然后检查它们是否全为1。具体来说枚举所有可能的正方形边长k从1到min(m,n)对于每个k枚举所有可能的左上角位置(i,j)检查以(i,j)为左上角边长为k的正方形是否全为1如果是计数器加1这种解法的时间复杂度是O(mnmin(m,n)^2)对于较大的矩阵效率极低。2.2 暴力解法的实现def countSquares(matrix): m, n len(matrix), len(matrix[0]) count 0 for k in range(1, min(m, n) 1): for i in range(m - k 1): for j in range(n - k 1): all_ones True for x in range(i, i k): for y in range(j, j k): if matrix[x][y] ! 1: all_ones False break if not all_ones: break if all_ones: count 1 return count注意这种暴力解法在LeetCode上会超时仅用于理解问题本质。3. 动态规划解法3.1 动态规划思路更高效的解法是使用动态规划。我们可以定义dp[i][j]表示以(i,j)为右下角的正方形的最大边长同时也是以(i,j)为右下角的正方形数量。状态转移方程如果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最终结果是所有dp[i][j]的和。3.2 为什么这个状态转移方程有效这个状态转移方程的核心思想是一个位置能构成的正方形大小取决于它上方、左方和左上方的邻居。具体来说dp[i-1][j]上方格子能构成的最大正方形边长dp[i][j-1]左方格子能构成的最大正方形边长dp[i-1][j-1]左上方格子能构成的最大正方形边长取这三个值的最小值再加1是因为新的正方形必须同时满足这三个方向的条件。3.3 动态规划实现def countSquares(matrix): m, n len(matrix), len(matrix[0]) dp [[0]*(n1) for _ in range(m1)] count 0 for i in range(1, m1): for j in range(1, n1): if matrix[i-1][j-1] 1: dp[i][j] min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) 1 count dp[i][j] return count这个解法的时间复杂度是O(mn)空间复杂度也是O(mn)可以通过滚动数组优化空间复杂度到O(n)。4. 空间优化解法4.1 滚动数组技巧我们可以观察到dp[i][j]只依赖于当前行和前一行因此可以使用滚动数组来优化空间def countSquares(matrix): m, n len(matrix), len(matrix[0]) prev [0]*(n1) count 0 for i in range(1, m1): curr [0]*(n1) for j in range(1, n1): if matrix[i-1][j-1] 1: curr[j] min(prev[j], curr[j-1], prev[j-1]) 1 count curr[j] prev curr return count4.2 进一步空间优化甚至可以只使用一维数组def countSquares(matrix): m, n len(matrix), len(matrix[0]) dp [0]*(n1) count 0 for i in range(m): prev 0 for j in range(n): temp dp[j1] if matrix[i][j] 1: dp[j1] min(dp[j], dp[j1], prev) 1 count dp[j1] else: dp[j1] 0 prev temp return count这种优化将空间复杂度降到了O(n)在实际面试中如果能写出这种解法会大大加分。5. 算法正确性证明5.1 数学归纳法证明我们可以用数学归纳法来证明这个动态规划解法的正确性基本情况对于第一行和第一列dp[i][j]只能是0或1这与实际情况一致。归纳假设假设对于所有ii和jjdp[i][j]计算正确。归纳步骤对于dp[i][j]它依赖于dp[i-1][j], dp[i][j-1], dp[i-1][j-1]根据归纳假设这些值都是正确的。取最小值再加1确保了新正方形的边界条件。5.2 实际案例验证以前面的例子为例[ [0,1,1,1], [1,1,1,1], [0,1,1,1] ]dp矩阵计算如下[ [0,1,1,1], [1,1,2,2], [0,1,2,3] ]总和为01111122012315与预期一致。6. 常见错误与调试技巧6.1 边界条件处理常见错误包括忘记处理matrix为空的情况行列索引处理不当导致越界dp数组大小设置错误应该比matrix大1调试技巧打印dp矩阵中间结果对小规模测试用例手动计算验证6.2 初始化问题dp数组通常需要初始化为0但要注意有些语言中数组初始化可能有默认值确保dp[0][j]和dp[i][0]都为06.3 状态转移错误常见错误忘记加1取min的三个参数顺序错误对matrix[i][j]0的情况没有重置dp[i][j]7. 复杂度分析7.1 时间复杂度暴力解法O(mnmin(m,n)^2)DP解法O(m*n)空间优化DPO(m*n)时间O(n)或O(1)空间7.2 空间复杂度原始DPO(m*n)滚动数组O(n)进一步优化O(n)或O(1)8. 类似题目与扩展8.1 LeetCode类似题目最大正方形只找最大的全1正方形最大矩形扩展到矩形情况统计全1子矩形统计所有全1矩形8.2 问题变种统计全0正方形子矩阵统计特定模式的正方形子矩阵三维矩阵中的立方体统计8.3 实际应用场景图像处理中的特征检测计算机视觉中的物体识别数据挖掘中的模式发现9. 刷题建议与技巧9.1 如何识别动态规划问题问题可以分解为子问题子问题有重叠有最优子结构性质9.2 动态规划解题步骤定义dp数组的含义找出状态转移方程确定初始条件考虑优化空间9.3 调试技巧画图辅助理解打印中间结果从小例子入手10. 个人心得与总结这道题是动态规划的经典应用关键在于理解dp[i][j]的定义和状态转移方程。在实际刷题中我有以下几点体会不要一开始就追求最优解先想出暴力解法再优化动态规划问题中dp数组的定义至关重要空间优化往往可以最后考虑先保证正确性多画图有助于理解状态转移过程对于想系统学习动态规划的同学建议从LeetCode的热门100题开始逐步建立解题思维。这道题作为动态规划的中等难度题目非常适合用来检验对DP的理解程度。