2025-08-20 09:08:13 +0000 UTC

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        rows, cols = len(matrix), len(matrix[0])
        dp = [[0] * (cols + 1) for _ in range(rows + 1)]
        res = 0
        for row in range(rows):
            for col in range(cols):
                val = matrix[row][col]
                if val == 0:
                    continue
                dp_row, dp_col = row + 1, col + 1
                dp_val = min(
                    dp[dp_row - 1][dp_col], 
                    dp[dp_row][dp_col - 1], 
                    dp[dp_row - 1][dp_col - 1]
                ) + 1
                dp[dp_row][dp_col] = dp_val
                res += dp_val
        return res