221.最大平方题目来源：https://leetcode-cn.com/problems/maximal-square题目在一个由0和1组成的二维矩阵中，只找到1并返回它的面积。例子：输入：10100101111111110010输出：4解题思路：动态规划本文利用动态规划的原理来解决这个问题。我们使用dp(i,j)表示以(i,j)为右下角且仅包含1的正方形的最大边长。如果能得到所有的dp(i,j)值，最大值就是最大正方形的边长，它的正方形就是我们需要的面积。根据题目要求，在给定的二维矩阵中，只有包含1的才能构成正方形。如果dp(i,j)=0，讨论是否可以组成一个正方形，求最长边是没有意义的，因为这个位置不可能在1组成的正方形中。那么如果位置为1，则需要考虑三个位置的情况，如下图：先看形成正方形的情况，结合上图，如果当前值为1，那么求最长的边，需要考虑从当前位置，top、left、upperleft的值必须为1，只有这样，再加上当前位置，才有可能组成一个正方形。即三个方向都不能为0。但是如果当前位置为1，但是限制了三个方向，三个方向的边不一定相同，那么所形成的正方形的边长需要为三者的最短边加1，表示加上当前s的位置。具体如上图所示，上面的数字表示正方形右下角的最大边长，其中？将正方形区域表示为右下角。左图中，受左上角0的限制，这里可以形成的正方形的最长边是3。中间的插图中，这里可以形成的正方形的最长边是2，有限上边0。在最后一个图中，这里可以形成的正方形的最长边是2，受左边0的约束。可以看出，得到的最长边是top、left、topleft正方形中最小的边长+1。所以状态转移方程为：dp(i,j)=min(dp(i-1,j),dp(i-1,j-1),dp(i,j-1))+1那么具体code实现如下。代码实现类解决方案：defmaximalSquare(self,matrix:List[List[str]])->int:iflen(matrix)==0:return0rows=len(matrix)cols=len(matrix[0])max_side=0dp=[[0]*colsfor_inrange(rows)]foriinrange(rows):forjinrange(cols):#当前值为1时，考虑求最长Sideif矩阵[i][j]=='1':#当前值为1，在第一行第一列时，如果i==0orj==则不考虑左上左上方向0:dp[i][j]=1否则:dp[i][j]=min(dp[i-1][j],dp[i-1][j-1],dp[i][j-1])+1max_side=max(max_side,dp[i][j])square=max_side**2returnsquare达到效果上面是用动态规划求最长边然后求解主要《221. 最大正方形》问题的内容。欢迎关注微信公众号《书所集录》
