题解 | #最大正方形#

【二维dp】 dp[i][j]表示以(i,j)为右下角的最大正方形的边长

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最大正方形
# @param matrix char字符型二维数组 
# @return int整型
#
class Solution:
    def solve(self , matrix: List[List[str]]) -> int:
        # write code here
        if len(matrix)==0 or len(matrix[0])==0:return 0
        dp=[[0 for i in range(len(matrix[0]))] for _ in range(len(matrix))]
        res=0
        for i in range(len(matrix)):
            if matrix[i][0]=='1':
                dp[i][0]=1
                res=max(res,dp[i][0])
        for j in range(len(matrix[0])):
            if matrix[0][j]=='1':
                dp[0][j]=1
                res=max(res,dp[0][j])
        for i in range(1,len(matrix)):
            for j in range(1,len(matrix[0])):
                if matrix[i][j]=='0':
                    dp[i][j]=0
                elif matrix[i][j]=='1':
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
                    res=max(res,dp[i][j])
        return res**2