# Leetcode 1277. Count Square Submatrices with All Ones

## 題解

### DP

#### 狀態轉移公式

dp[_y][_x] = min(
    dp[_y-1][_x-1], # top left
    dp[_y-1][_x], #  top
    dp[_y][_x-1], # left
) + 1 if matrix[y][x] == 1 else 0

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        # Time complexity: O(mn)
        # Space complexity: O(mn)
        m,n = len(matrix),len(matrix[0])
        dp = [[0 for i in range(n+1)] for i in range(m + 1)]
        output = 0
        for y in range(m):
            for x in range(n):
                _y,_x = y+1,x+1
                dp[_y][_x] = min(
                    dp[_y-1][_x-1], # top left
                    dp[_y-1][_x], #  top
                    dp[_y][_x-1], # left
                ) + 1 if matrix[y][x] == 1 else 0
                output += dp[_y][_x]
        return output

### 狀態壓縮

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        # Time complexity: O(mn)
        # Space complexity: O(n)
        m,n = len(matrix),len(matrix[0])
        dp = [0 for i in range(n+1)]
        output = 0
        for y in range(m):
            top_left = 0
            for x in range(n):
                _x = x+1
                origin_top_left = top_left
                top_left = dp[_x]
                dp[_x] = min(
                    origin_top_left, # top left
                    dp[_x], #  top
                    dp[_x-1], # left
                ) + 1 if matrix[y][x] == 1 else 0
                output += dp[_x]
        return output