# Count Square Submatrices with All Ones

maximum square length 的增强版

![](https://1824821017-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M3rU5fVRA3qiBmK8Dbx%2F-M7qvUnj3VJPkgh68xW9%2F-M7qvZ6m-LMn_e5jtykY%2FScreen%20Shot%202020-05-21%20at%204.10.55%20AM.png?alt=media\&token=2059490b-0b77-4c2d-987b-3c5deada1be6)

```python
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:

```python
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
```