Count Square Submatrices with All Ones

https://leetcode.com/explore/featured/card/may-leetcoding-challenge/536/week-3-may-15th-may-21st/3336/

maximum square length 的增强版

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        res=0
        m,n = len(matrix),len(matrix[0])
        dp=[[0]*n for _ in range(m)]
        if matrix[0][0] == 1:
            dp[0][0]=1
            res+=1
        for i in range(1,m):
            if matrix[i][0] == 1:
                dp[i][0] = 1
                res+=1
        
        for j in range(1,n):
            if matrix[0][j] == 1:
                dp[0][j] = 1
                res+=1
        
        for i in range(1,m):
            for j in range(1,n):
                if matrix[i][j] == 1:
                    dp[i][j] = min([dp[i][j-1],dp[i-1][j],dp[i-1][j-1]]) + 1
                    res += dp[i][j]
                
        return res

Simplified version:

class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        res=0
        m,n = len(matrix),len(matrix[0])
        dp=[[0]*n for _ in range(m)]
       
        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
                        res+=1
                    else:
                        dp[i][j] = min([dp[i][j-1],dp[i-1][j],dp[i-1][j-1]]) + 1
                        res += dp[i][j]
                
        return res