221. 最大正方形
题目来源：https://leetcode-cn.com/problems/maximal-square
题目
在一个由 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(i, j) 表示以 (i, j) 为右下角，且只包含 1 的正方形的边长最大值。如果能够求出所有的 dp(i, j) 值，其中最大值就是最大正方形的边长，其平方就是我们要求的面积。
根据题意要求，所给的二维矩阵内，只有包含 1 的才能构造正方形。如果 dp(i, j) =为 0 的情况下，讨论是否能够构成正方形并求出最长边就没有意义，因为这位置不能在构成由 1 组成的正方形中。
那么如果该位置为 1 的情况下，就需要考虑三个位置的情况，如下图：
先看下构成正方形的情况，结合上面的图示，如果当前的值为 1，那么要找出最长的边，就需要考虑从当前位置出发，上面，左边，左上的值都必须是 1，只有这样，再加上当前位置才有可能构成正方形。
也就是说，这三个方向都不能是 0。但是如果当前位置为 1，但三个方向受限制的情况下，三个方向的边不一定都一样，那么构成的正方形的边长则需要取三者最短边，再加 1，表示加上当前的位置。
具体如上示图，上面的数字表示以此为正方形右下角的最大边长，其中 ？ 表示作为右下角的正方形区域。
其中左图，受左上角 0 的限制，这里可构成的正方形的最长边为 3。
中间的图例中，受上边 0 的限制，这里可构成的正方形的最长边为 2。
最后的图例中，受左边 0 的限制，这里可构成的正方形的最长边为 2。
可以看出，得出的最长边都是上，左，左上三个正方形中最小边长 + 1。
所以状态转移方程为：
dp(i, j) = min(dp(i-1, j), dp(i-1, j-1), dp(i, j-1)) + 1
那么具体的代码实现如下。
代码实现
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if len(matrix) == 0:
return 0
rows = len(matrix)
cols = len(matrix[0])
max_side = 0
dp = [[0] * cols for _ in range(rows)]
for i in range(rows):
for j in range(cols):
# 当前的值为 1 时，考虑求构成正方形的最长边
if matrix[i][j] == '1':
# 当前值为 1，处于首行首列时，不考虑左，上，左上三个方向
if i == 0 or j == 0:
dp[i][j] = 1
else:
dp[i][j] = min(dp[i-1][j], dp[i-1][j-1], dp[i][j-1]) + 1
max_side = max(max_side, dp[i][j])
square = max_side ** 2
return square
实现效果
以上就是使用动态规划，找出最长边，进而解决《221. 最大正方形》问题的主要内容。
欢迎关注微信公众号《书所集录》
