[二维前缀和]1277. 统计全为 1 的正方形子矩阵
1277. 统计全为 1 的正方形子矩阵
问题是计算一个二进制矩阵中所有由1组成的正方形的数量。函数名为countSquares，输入是二维列表matrix，输出是整数。
解决方案使用动态规划。我们创建一个二维数组f，其维度比matrix多一行和一列，即(m+1) x (n+1)，初始化为0。
f[i][j]表示以(i-1, j-1)为右下角的最大正方形的边长。因为f的索引从1开始，对应matrix的0索引。
遍历matrix中的每个元素，如果当前元素x为1，则更新f[i+1][j+1] = min(f[i][j], f[i][j+1], f[i+1][j]) + 1。这个公式的意思是，以当前点为右下角的正方形边长取决于其左上、左和上三个点的最小边长加1。这是因为要形成更大的正方形，需要这三个方向都能形成较小的正方形。
最后，返回f数组中所有元素的和。因为f[i][j]表示以(i-1, j-1)为右下角的最大边长，而这个值也等于以该点为右下角的正方形数量。例如，如果最大边长为k，那么就有k个正方形（边长为1,2,...,k）。
所以，sum(map(sum, f))就是所有正方形的总数。
该代码使用动态规划方法来计算二进制矩阵中所有由 1 组成的正方形的数量。以下是详细解释：
方法思路
- 1.问题分析：我们需要统计矩阵中所有由 1 组成的正方形的数量。这些正方形可以是任意大小，只要其元素全部为 1。
- 2.动态规划设置：创建一个二维数组
f，其维度为(m+1) × (n+1)，其中m和n是输入矩阵的行数和列数。f[i][j]表示以原始矩阵中位置(i-1, j-1)作为右下角的最大正方形的边长。 - 3.状态转移：对于每个元素
matrix[i][j]，如果值为 1，则f[i+1][j+1]的值由其左上、左和上三个相邻的f值中的最小值加 1 决定。这确保了只有当这三个方向都能形成正方形时，当前点才能形成更大的正方形。 - 4.结果计算：最终结果是
f数组中所有元素的和，因为f[i][j]的值不仅表示最大边长，还表示以该点为右下角的不同大小的正方形数量（例如，边长为k的正方形对应k个正方形）。
解决代码
from typing import Listclass Solution:def countSquares(self, matrix: List[List[int]]) -> int:m, n = len(matrix), len(matrix[0])f = [[0] * (n + 1) for _ in range(m + 1)]for i, row in enumerate(matrix):for j, x in enumerate(row):if x:f[i + 1][j + 1] = min(f[i][j], f[i][j + 1], f[i + 1][j]) + 1return sum(map(sum, f))代码解释
- 1.初始化：
f数组被初始化为一个(m+1) x (n+1)的零矩阵，用于存储动态规划状态。 - 2.遍历矩阵：对于每个元素
matrix[i][j]，如果值为 1，则计算f[i+1][j+1]的值。该值取决于其左上、左和上三个方向的f值的最小值加 1。 - 3.返回结果：通过求和
f数组中的所有元素，得到所有正方形的总数，因为每个f值代表了以该点为右下角的正方形数量。
这种方法通过动态规划高效地统计了所有可能的正方形，时间复杂度为 O(m*n)，适用于大多数实际场景。
为什么这个min操作确保了只有当左上、左和上三个方向都能形成正方形时，当前点才能形成更大的正方形？
- f[i][j] 代表左上角方向的正方形大小，这对应于当前正方形左上角的部分。
- f[i][j+1] 代表上边方向的正方形大小，这对应于当前正方形上边的部分。
- f[i+1][j] 代表左边方向的正方形大小，这对应于当前正方形左边的部分。
为了形成一个以(i,j)为右下角的更大的正方形，必须确保左边、上边和左上边都能支持这个正方形。也就是说，如果左边有一个边长为k的正方形，上边有一个边长为k的正方形，左上边有一个边长为k的正方形，那么当前点可以形成一个边长为k+1的正方形。但如果其中任何一个方向的正方形边长小于k，那么当前点只能形成以最小边长为基准的正方形。
因此，取最小值 确保我们被最小的外接正方形所限制。如果三个方向的最小值是k，那么当前点只能形成边长为k+1的正方形。这意味着如果任何一个方向不能支持更大的正方形，当前点形成的正方形也会受到限制。
假设f[i][j] = 2, f[i][j+1] = 3, f[i+1][j] = 3。那么min是2，所以f[i+1][j+1] = 2 + 1 = 3。这意味着以(i,j)为右下角的最大正方形边长为3。
为什么？因为要形成边长为4的正方形，需要左边有边长为3的正方形，上边有边长为3的正方形，左上边有边长为3的正方形。但左上边只有边长为2，所以无法形成边长为4的正方形。因此，最大只能是边长为3。
所以，取最小值确实确保了当前点的正方形大小受限于最弱的邻居。
在代码中，f数组的索引偏移了1，所以f[i+1][j+1]对应matrix[i][j]。
最终，返回所有f值的和，因为f[i][j]的值表示以该点为右下角的最大正方形的边长，同时这个值也等于以该点为右下角的不同大小的正方形数量。例如，如果最大边长为3，那么就有边长为1、2、3的三个正方形，所以贡献3个正方形。
因此，在解释时，我需要强调min操作如何反映三个方向的约束。