题解 | #最大正方形#

[动态规划]

• 确定dp的相关信息
  • dp的维度--二维
  • dp[i][j]的意义--当(i,j)作为正方形的右下角时，正方形的边长
  • 初始化dp[i][0]、dp[0][j]
• 双层for循环给dp[i][j]赋值，复杂度O(n^2)
• 因为dp[i][j]只与和他相邻的三个元素相关，所以可以将空间复杂度简化到O(1)

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 最大正方形
# @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