image.png

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # dp[i][j]=n 表示以i,j元素为正方形右下角的最大正方形边长
        # dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) + 1 if matrix[i][j]==1 else 0
        m = len(matrix)
        n = len(matrix[0])
        max_ = 0
        dp = [[0]*n for _ in range(m)]
        for i in range(m):
            for j in range(n):
                x = dp[i][j-1] if j-1>=0 else 0
                y = dp[i-1][j] if i-1>=0 else 0
                xy = dp[i-1][j-1] if i-1>=0 and j-1>=0 else 0
                dp[i][j] = min(x,y,xy)+1 if matrix[i][j]=='1' else 0
                if dp[i][j]>max_: max_ = dp[i][j]
        return max_**2

优化

用padding 在第一行和第一列之前补上一行一列，就可以避免对边界的逻辑判断 但这样会使得空间变大

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        # dp[i][j]=n 表示以i,j元素为正方形右下角的最大正方形边长
        # dp[i][j] = min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) + 1 if matrix[i][j]==1 else 0
        m = len(matrix)
        n = len(matrix[0])
        max_ = 0
        dp = [[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                x = dp[i][j-1]
                y = dp[i-1][j]
                xy = dp[i-1][j-1]
                dp[i][j] = min(x,y,xy)+1 if matrix[i-1][j-1]=='1' else 0
                if dp[i][j]>max_: max_ = dp[i][j]
        return max_**2