其实以前写过
但我也忘记以前怎么写的了
总之
把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)])