【动态规划-矩阵】6.最大正方形

题目

难度： 中等
题目内容：
在一个由 ‘0’ 和 ‘1’ 组成的二维矩阵内，找到只包含 ‘1’ 的最大正方形，并返回其面积。
示例1：

输入：matrix = [[“1”,“0”,“1”,“0”,“0”],[“1”,“0”,“1”,“1”,“1”],[“1”,“1”,“1”,“1”,“1”],[“1”,“0”,“0”,“1”,“0”]]
输出：4

示例2：

输入：matrix = [[“0”,“1”],[“1”,“0”]]
输出：1

前置思路

拿到题最直觉的思路就是遍历当遇到‘1’则进行展开获取以该点为顶点的，向右，向下展开后的最大边长，并将最大边长保存下来，最后返回最大边长的乘积。但这个 思路有个很明显的问题就是会存在很多重复计算的过程。
如果将这个过程用动态规划的思路简化是关键。
首先以2*2的正方形，找到最大边长的过程进行描述：
1.找到某个顶点，该顶点处于左上角，当前正方形最大边长就是1
2.此时只需要找与该点相邻的右点，下点，以及右下点，确认他们是否都是1即可
3.相对的，右下点的相邻上点，左点，以及左上点也都是1

可以推测，找到最大正方形的关键是正方形的对角线，且对角线的每个点都可以通过左上点的最大正方形边长+1来更新最大边长，前提是新的两条边都能填满。

那么先做一个假设，假设每一点都能记录下到该点（该点向左上延伸）的最大正方形边长，当且仅当某一点的左，上，左上能组成的最大正方形边长相等，才能使得最大正方形的边长+1。

进一步简化这个思路，某一个点所能组成的最大正方形边长（该点向左上延伸），（为相邻三点所能组成最大正方形边长的最小值）+1，因为更大值可以向下兼容，抽出某些部分结合新的点组成新的正方形。

代码

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        n = len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        # 记录最大正方形的边长
        maxLen = 0
        # 边界值计算
        for i in range(m):
            if matrix[i][0] == "1":
                dp[i][0] = 1
                maxLen = 1
            else:
                dp[i][0] = 0
        for j in range(1,n):
            if matrix[0][j] == "1":
                dp[0][j] = 1
                maxLen = 1
            else:
                dp[0][j] = 0
        for i in range(1,m):
            for j in range(1,n):
                # 如果为“1”则使用状态转移方程来记录该点最大边长，并判断当前最大边长
                if matrix[i][j] == "1":
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
                    maxLen = dp[i][j] if dp[i][j] > maxLen else maxLen
                else:
                    dp[i][j] = 0
        return maxLen * maxLen

思考

这题的前置思考已经描述得比较详细了，大致是我得思路过程，从正向的方法，再利用状态的转移来考虑如何记录下有效的状态，有效的状态既可以被新的条件转移，又可以计算出最终的结果。
这里比较关键的，我认为有两点：
1.发现对角线是判断正方形成立的关键
2.理解当某一点能形成的最大正方形，其部分能够被相邻点利用