https://leetcode-cn.com/explore/interview/card/bytedance/246/dynamic-programming-or-greedy/1028/
image.png
動態(tài)規(guī)劃的思路
其實所有動態(tài)規(guī)劃的思路，都是要找規(guī)律壶熏。這個題只要找到了規(guī)律句柠，就很簡單。
對于每個節(jié)點 a[i][j]，加入他為1溯职，那么他能組成的最大正方形的邊長精盅，取決于他周邊的幾個節(jié)點a[i-1][j],a[i][j-1],a[i-1][j-1]，如果這三個都能組成邊長為2的正方形谜酒，那么加上他叹俏，就變成了邊長為3的正方形。但是這三個有1個不能組成甚带，那么加上這個節(jié)點也無法組成她肯。
所以 a[i][j] = min(a[i-1][j],a[i][j-1],a[i-1][j-1]) + 1
然后正方形的面積就是周長的平方佳头。
代碼如下：
class Solution(object):
def maximalSquare(self, matrix):
"""
:type matrix: List[List[str]]
:rtype: int
"""
if not matrix:
return 0
pos = []
for i in range(0,len(matrix)):
pos.append([0]*len(matrix[i]))
# 對第一行賦值：
result = 0
for i in range(0,len(matrix[0])):
if matrix[0][i]=='1':
pos[0][i] = 1
result = 1
# 對第一列賦值
for i in range(0,len(matrix)):
if matrix[i][0] == '1':
pos[i][0] = 1
result = 1
for i in range(1,len(matrix)):
for j in range(1,len(matrix[0])):
if matrix[i][j] == '1':
pos[i][j] = min(pos[i-1][j],pos[i][j-1],pos[i-1][j-1]) + 1
result = max(result,pos[i][j]*pos[i][j])
return result
