↓Skip to main content
  1. Posts/

LeetCode-221 最大正方形

·1 min·
Table of Contents

LeetCode-221 最大正方形 #

Solution 1 #

用 $dp[i][j]$ 代表以 $(i, j)$ 为右下角的最大正方形的边长, 动态规划.

代码如下:

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0 for _ in range(n)] for _ in range(m)]
        ans = 0
        for i in range(m):
            for j in range(n):
                d1 = dp[i - 1][j] if i > 0 else 0
                d2 = dp[i][j - 1] if j > 0 else 0
                d3 = dp[i - 1][j - 1] if i > 0 and j > 0 else 0
                dp[i][j] = 0 if matrix[i][j] == '0' else 1 + min(d1, d2, d3)
                ans = max(dp[i][j], ans)
        return ans ** 2