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

闪念标签：LC

题目链接：https://leetcode.cn/problems/count-square-submatrices-with-all-ones/