难度: Medium
给你一个 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 <= 3001 <= arr[0].length <= 3000 <= arr[i][j] <= 1运行时间: 98 ms
内存: 18.6 MB
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
#动态规划
dp = [[0] * n for _ in range(m)]
ans = 0
for i in range(m):
for j in range(n):
if matrix[i][j] == 1:
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
ans += dp[i][j]
return ans
本题解采用动态规划的方法来解决问题。我们设一个与输入矩阵相同大小的DP表，dp[i][j]表示以(i, j)为右下角的正方形的最大边长。对于每个1在矩阵中的位置，如果它是第一行或第一列的一部分，它只能形成边长为1的正方形（即本身）。对于其他位置，如果matrix[i][j]是1，dp[i][j]将基于其左方(dp[i][j-1])、上方(dp[i-1][j])以及左上方(dp[i-1][j-1])的dp值，取这三个值中的最小值然后加1。这确保了只计算完全由1组成的正方形。最后，将所有dp[i][j]的值累加，即得到所有可能的正方形数量。
时间复杂度: O(m*n)
空间复杂度: O(m*n)
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0]) # m, n分别为矩阵的行数和列数
dp = [[0] * n for _ in range(m)] # 初始化DP表
ans = 0 # 初始化计数器
for i in range(m):
for j in range(n):
if matrix[i][j] == 1: # 只有当当前位置是1时，才可能构成正方形
if i == 0 or j == 0: # 边界情况处理，第一行或第一列
dp[i][j] = 1
else: # 非边界情况下，取左，上，左上三个位置的最小值加1
dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]) + 1
ans += dp[i][j] # 将当前位置的正方形数量加到结果中
return ans # 返回总的正方形数量
dp数组中的每个元素dp[i][j]代表以(i, j)为右下角的最大正方形的边长。初始化为0是因为在动态规划的开始阶段，我们尚未开始计算任何正方形的大小。直接使用矩阵的值会引入误解，因为矩阵的值1只表示该位置有一个单独的1，并不代表那里已经有一个正方形。dp数组的值是基于一系列条件计算得出的结果，而不仅仅是单个元素的值。
这种更新策略确保了只有当一个单元格的左侧、上方和左上方三个相邻位置都至少能形成某一大小的正方形时，当前位置才能形成更大的正方形。取最小值加1的逻辑是因为正方形的形成是受到最短边的限制。例如，如果左侧、上方和左上方的正方形边长分别是2, 3, 2，则只能以当前位置形成边长为3的正方形（2+1=3），因为边长超过2的正方形会在某个方向上缺少支持。
这种处理保证了正确性，因为第一行和第一列的元素没有足够的上方或左方空间来形成大于1x1的正方形。因此，如果这些位置的元素是1，它们自身就是一个边长为1的正方形。这种处理简化了边界条件的处理，避免了在循环中进行不必要的边界检查。
不完全是这样。虽然实际形成的新正方形的边长是由三个方向中的最小边长决定的，但这三个方向的正方形边长不必完全相同。只要这三个位置的正方形边长都至少达到某个值，就可以在此基础上形成一个较大的正方形。例如，如果这三个方向的正方形边长分别是2, 3, 和2，则可以在这个位置形成一个3x3的正方形，因为所有方向都支持至少2x2的正方形，再加上该位置本身的1，形成3x3正方形。