221. 最大正方形

来源: 221. 最大正方形

1. 题目描述

在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。

2. 解题思路

动态规划，dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1

3. 代码

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if(not matrix):
            return 0
        m=len(matrix)
        n=len(matrix[0])
        res=0
        dp=[[0]*(n+1) for _ in range(m+1)]
        for i in range(1,m+1):
            for j in range(1,n+1):
                if(matrix[i-1][j-1]=="1"):
                    dp[i][j]=min(dp[i-1][j-1],dp[i-1][j],dp[i][j-1])+1
                    res=max(dp[i][j],res)
        return res*res


# 参考：wu_yan_zu
# 链接：https://leetcode-cn.com/problems/maximal-square/solution/dong-tai-gui-hua-kong-jian-you-hua-zhu-xing-jie-2/