最大正方形

最大正方形_牛客题霸_牛客网

问题简述

给定一个由'0'和'1'组成的2维矩阵，返回该矩阵中最大的由'1'组成的正方形的面积，输入的矩阵是字符形式而非数字形式。

思路：动态规划

• 定义 dp(i, j) := 以坐标(i,j)为右下角的最大正方形边长

• 则 dp(i, j) = min( dp(i-1,j), dp(i,j-1), dp(i-1,j-1) ) + 1，当 matrix[i-1][j-1] == 1 时；

Python 写法1：递归

class Solution:
    def solve(self , matrix: List[List[str]]) -> int:
        if not matrix: return 0
        
        self.mx = 0
        
        from functools import lru_cache
        @lru_cache(maxsize=None)
        def dp(i, j):  # 以坐标(i,j)为右下角的最大正方形边长
            if i == 0 or j == 0: return 0
            r1, r2, r3 = dp(i - 1, j), dp(i, j - 1), dp(i - 1, j - 1)
            if matrix[i - 1][j - 1] == '1':
                ret = min(r1, r2, r3) + 1
                self.mx = max(self.mx, ret)
                return ret
            return 0
        
        m, n = len(matrix), len(matrix[0]) 
        dp(m, n)
        return self.mx ** 2

Python 写法2：迭代

class Solution:
    def solve(self , matrix: List[List[str]]) -> int:
        if not matrix: return 0
        
        self.mx = 0
        m, n = len(matrix), len(matrix[0]) 
        dp = [[0] * (n + 1) for _ in range(m + 1)]
        
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                r1, r2, r3 = dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]
                if matrix[i - 1][j - 1] == '1':
                    ret = min(r1, r2, r3) + 1
                    self.mx = max(self.mx, ret)
                    dp[i][j] = ret
        
        return self.mx ** 2