221. 最大正方形

难度中等428

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

示例:

1
2
3
4
5
6
7
8
输入: 

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

输出: 4

神必的dp

主要是状态的寻找,这题的状态是:$dp[i][j]$表示i,j点为右下角的矩形的最大宽度;

状态转移方程比较难像:

$dp[i][j]=min(dp[i][j-1],dp[i-1][j],dp[i-1][j-1])$

解释如下:

image-20200531160513652
image-20200531160513652

为了代码的美观减少一次特判,应该要在左边和上边多加一列:

0 0 0 …..

0 matrix

0

…

python代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution:
    #重点是神必的状态转移方程
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        if len(matrix) ==0:
            return 0
        height=len(matrix)
        width=len(matrix[0])
        dp=[[0 for i in range(width+1)] for j in range(height+1)]
        #dp初始化,并且在外面多套了一层;
        #dp[i,j]表示以i,j为右下角的矩形的最大宽度;
        # 0 0 0 0 ....
        # 0 matrix
        # 0
        # 0
        # ...
        #转移方程:dp[i,j]=min(dp[i-1,j],dp[i,j-1],dp[i-1,j-1])+1
        maxedge=0
        for i in range(height):
            for j in range(width):
                if matrix[i][j]=='1':
                    dp[i+1][j+1]=min(dp[i][j],dp[i+1][j],dp[i][j+1])+1
                maxedge=max(maxedge,dp[i+1][j+1])
        return maxedge*maxedge