221. 最大正方形
思路：
- 坐标型动态规划，找到规律一切就都迎刃而解了。
- 话不多说，一图胜千言。
![fig1]
根据上面可以直接得到状态转移方程，fi代表的是以该位置为正方形的右下角则最大正方形的边长。
- 时间复杂度O（N M），空间复杂度O（N M）
- 这题唯一的缺点是输入的元素用的字符串
python3代码
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