其實以前寫過
但我也忘記以前怎麼寫的了
總之
把matrix[i][j]變成: 以(i,j)為最右下角畫出的最大正方形的邊長
最後sum(matrix)就是答案了
def countSquares(self, matrix: List[List[int]]) -> int:
m, n = len(matrix), len(matrix[0])
#dp
for i in range(1, m):
for j in range(1, n):
if matrix[i][j]>0:
matrix[i][j] = min(matrix[i-1][j-1], matrix[i-1][j],
matrix[i][j-1])+1
return sum([sum(matrix[i]) for i in range(m)])