题目大意，给定一个矩阵，元素为0或者1. 求所有元素都为1的最大正方形子矩阵。把它跟第85题放在一起，85题求最大的长方形子矩阵。
详细的讲解，请参考[解题报告] LeetCode 221. Maximal Square
brute force
对每一行(y)，对每一列(x)，对所有可能的size，检查以(y, x)为顶点，大小为size的区域是不是符合要求。对检查函数必须做优化，否则会TLE.
for y in range(m):
for x in range(n):
for size in range(1, min(n - x, m - y)):
check(matrix, x, y, x + size, y + size)
matrix = [[1, 0, 1, 0, 0], [1, 0, 1, 1, 1], [1, 1, 1, 1, 1], [1, 0, 0, 1, 0]]
动态规划
对每一行(y)，对每一列(x)，对所有可能的size，检查以(y, x)为顶点，大小为size的区域是不是符合要求。
设置一个检查函数来降低时间复杂度：如图所示，把面积简化成从(0, 0)开始的几个长方形/正方形的面积的加减。
而求从(0, 0)开始的任意的面积可以使用DP在时间复杂度为\(O(m * n)\)的范围内解出来。
最后的code如下。\(sums[i][j]\)表示从\((0, 0)\)到\((i, j)\)的面积。
class Solution(object):
def maximalSquare(self, matrix):
m = len(matrix)
if m == 0:
return 0
n = len(matrix[0])
# sums[i][j] = sum(matrix[0][0] ~ matrix[i-1][j-1])
sums = [[0 for _ in range(n+1)] for _ in range(m+1)]
for i in range(1, m+1):
for j in range(1, n+1):
sums[i][j] = matrix[i-1][j-1] + sums[i-1][j] + sums[i][j-1] - sums[i-1][j-1]
ans = 0
for i in range(1, m+1):
for j in range(1, n+1):
for k in range(min(m-i+1, n-j+1), 0, -1):
sum = sums[i+k-1][j+k-1] - sums[i+k-1][j-1] - sums[i-1][j+k-1] + sums[i-1][j-1]
if sum == k*k:
ans = max(ans, sum)
break
return ans