Leetcode 221 最大正方形

题目传送门

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

示例:

输入:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

输出: 4

分析:

• 动态规划，问题转化成求最大正方形边长
• 建立二维矩阵dp[M][N]其中M, N分别为原二维矩阵的高和宽
• 矩阵中一点dp[i][j]表示以matrix[i][j]该点为右下角端点的最大正方形的变长，若matrix[i][j] == '0'则该端点无法构成正方形，记边长为0
• 矩阵中的每一个点作为正方形右下角端点所能构成最大正方形的边长，亦或是该点 左方、上方、左上方相邻端点所能构成最大正方形边长的最小值加1（该点为"1"），亦或为0（该点为0）
• 动态转移方程：
  dp[i][j] = min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1])+1 (该点为"1")
  dp[i][j] = 0 (该点为"0")

Python3代码：

class Solution:
    def maximalSquare(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if matrix == []: return 0 
        M, N = len(matrix), len(matrix[0])
        dp = [[0 for _ in range(N)]for _ in range(M)]
        Max = 0
        for i in range(N):   # dp矩阵初始化
            dp[0][i] = int(matrix[0][i])
            Max = max(dp[0][i], Max)
        for i in range(M):   # dp矩阵初始化
            dp[i][0] = int(matrix[i][0])
            Max = max(dp[i][0], Max)
        for i in range(1, M):
            for j in range(1, N):
                if matrix[i][j] == '0': continue
                dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1])+1
                Max = max(dp[i][j], Max)
        return Max**2