思路:
![fig1]
根据上面可以直接得到状态转移方程,fi代表的是以该位置为正方形的右下角则最大正方形的边长。
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
n = len(matrix)
if(n == 0):
return 0
m = len(matrix[0])
res = 0
for x in range(n):
for y in range(m):
if(x == 0 or y == 0):
matrix[x][y] = int(matrix[x][y])
res = max(res,matrix[x][y])
continue
else:
if(matrix[x][y] == "1"):
matrix[x][y] = min(matrix[x-1][y],matrix[x][y-1],matrix[x-1][y-1])+1
if(matrix[x][y] > res):
res = matrix[x][y]
else:
matrix[x][y] = 0
return res**2