这是我的第一篇测试文章

221. 最大正方形

思路：

1. 坐标型动态规划，找到规律一切就都迎刃而解了。
2. 话不多说，一图胜千言。

![fig1]

根据上面可以直接得到状态转移方程，fi代表的是以该位置为正方形的右下角则最大正方形的边长。

1. 时间复杂度O（N M），空间复杂度O（N M）
2. 这题唯一的缺点是输入的元素用的字符串

python3代码

代码语言：javascript复制

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

python3 动态规划 字符串

0 人点赞