【刷题记录 python】最大正方形

leetcode 221
关键：
（1）dp数组：遍历matrix中的每个元素，站在以遍历时的每个元素为正方形右下角的角度，dp在每个元素对应的位置上取正方形的边长为值。所以dp维度和matrix一样，元素取值含义为：以该元素为右下角的最正方形的边长
（2）递推公式：要确定正方形右下角元素对应的最大正方形边长，依赖该元素左边、上面、左上三个位置在dp数组中的取值。

• matrix[i][j] == “1” : dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
• 否则为0
  （3）初始化：递推公式涉及到-1的计算，因此初始化dp的第0行和第0列，当matrix对应元素为“1”时，dp对应位置取值为1
  （4）遍历顺序：因为递推公式考虑左、上、左上三个方向，因此按正序顺序遍历即可保证遍历到当前位置时，dp数组中左、上、左上位置的值已经更新过了。

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        r, c = len(matrix), len(matrix[0])
        dp = [[0]*c for _ in range(r)]
        max_record = 0
        #initial
        for j in range(c):
            if matrix[0][j] == "1":
                dp[0][j] = 1
                max_record = max(max_record,dp[0][j])
        for i in range(r):
            if matrix[i][0] == "1":
                dp[i][0] = 1
                max_record = max(max_record,dp[i][0])
        if r==1 or c == 1:
            return max_record
        for i in range(r):
            for j in range(c):
                if matrix[i][j] == "1":
                    dp[i][j] = min(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]) + 1
                    if dp[i][j] > max_record:
                        max_record = dp[i][j]
        return max_record**2