JZX轻语：简
LeetCode 1277 - 统计全为 1 的正方形子矩阵
发表于2024年07月16日
通过观察发现，如果一个正方形子矩阵的右下角是(i, j)，且边长为k，那么这个该正方形包含四个重叠的、边长为k - 1的正方形子矩阵，分别以(i - 1, j - 1)、(i - 1, j)、(i, j - 1)、(i, j)为右下角。
因此，我们可以定义dp[i][j]为以(i, j)为右下角的正方形子矩阵的最大边长，那么有状态转移方程dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1(如果matrix[i][j] == 1，否则为0)。最后，答案即为所有dp[i][j]的和。
class Solution:
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
ans = 0
dp = [[0] * n for _ in range(m)]
for i in range(m):
for j in range(n):
if not matrix[i][j]:
continue
dp[i][j] = min(
dp[i - 1][j] if i > 0 else 0, # 要注意边界条件, 下同
dp[i][j - 1] if j > 0 else 0,
dp[i - 1][j - 1] if i > 0 and j > 0 else 0
) + 1
ans += dp[i][j]
return ans