最大正方形
这道题首先看完题后我想的是可以创造出一个小于这个矩形的正方形然后依次遍历每个可能的位置 但是后来感觉太麻烦 于是 发现 这道题可以用dp来解决 如果以右下角为起点
那么就可以发现公式
1
| pos(i,j)=min(pos(i−1,j),pos(i−1,j−1),pos(i,j−1))+1
|
每一个方格的最大正方形边长数等于其左或上或右相邻方格其中的最小值+1 而其中情况可以分三种讨论
若方格处于左边界和上边界 那么其等于本身的数
若方格为0 则最大边长数直接为0
那么我们来写代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution(object):
def maximalSquare(self, matrix):
x = len(matrix)
y = len(matrix[0])
max_side = 0
dp_square = [[0 for i in range(y)] for i in range(x)]
for xx in range(x):
for yy in range(y):
if (matrix[xx][yy] == '1'):
if (xx == 0 or yy == 0):
dp_square[xx][yy] = 1
else:
dp_square[xx][yy] = min(dp_square[xx - 1][yy], dp_square[xx][yy - 1],dp_square[xx - 1][yy - 1]) + 1
max_side = max(0,dp_square[xx][yy], max_side)
result = max_side * max_side
return result
|
