最大正方形

Leetcode Link: 221. 最大正方形 - 力扣（LeetCode）

题目

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

解法一

思路：动态规划

为啥想到了动规？因为觉得写暴力，实在是麻烦。 如果一个点的左上角的点是一个正方形，那么只需要判断这个点向上向左走一走之后能不能构成正方形即可。

动规五步走

1. dp 内容：二维 dp, dp[i][j] 表示以 [i][j] 作为正方形的右下角，构成的最大正方形面积
2. 递推公式：
   1. 只有当 dp[i-1][j-1] 是正方形的时候，dp[i][j] 才可能是面积>1 的正方形。此时需要分别从 [i][j] 往上、左走，计算有多少个位置为 1，来判定 dp[i][j] 面积
   2. 当 dp[i-1][j-1] 不是正方形的时候，dp[i][j] 只取决 matrix[i][j] 的值
3. 初始化：可以直接初始化第一行和第一列
4. 遍历顺序：从左到右，从上到下即可
5. 写一个dp表出来。

题解：

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        dp = [[None for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
        row = len(matrix)
        col = len(matrix[0])
 
        for i in range(row):
            dp[i][0] = 1 if matrix[i][0] == '1' else 0
        for j in range(col):
            dp[0][j] = 1 if matrix[0][j] == '1' else 0
 
        for i in range(1, row):
            for j in range(1, col):
                if dp[i-1][j-1] >= 1 and matrix[i][j] == '1':
                    bc = int (sqrt (dp[i-1][j-1])) # 斜上正方形的边长
                    # -- 这一小块，debug了半个多小时，务必重新写 ----
                    cnt = 1   # 当前的计数，用来计算边长
                    while(cnt < bc+1):
                        if matrix[i-cnt][j] != '1' or matrix[i][j-cnt] != '1':
                            break
                        cnt += 1
                    dp[i][j] = (cnt)**2
                else:
                    dp[i][j] = 1 if matrix[i][j] == '1' else 0
        
        return max([max(row) for row in dp])
 

启发和联系

务必查看官方解法。