最大正方形

这道题使用动态规划来解决。定义二维dp数组，其中dp[i][j]表示以(i,j)为右下角的正方形的最大边长。状态转移方程为：当前位置如果为'1'，则dp[i][j] = min(左上角dp值, 正上方dp值, 正左方dp值) + 1。最后返回dp数组中的最大值的平方即为最大正方形面积。

时间复杂度: O(mn)

空间复杂度: O(mn)

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        """
        dp数组含义：
        dp[i][j]代表着，i,j处所能构成最大正方形的最大边长
        递推公式：
            if matrix[i][j] == '1':
                dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1])+1
        初始化：
            第0行和第0列值为1需要进行初始化为1
        遍历顺序：
            从左到右，从上到下，正序
        """
        m = len(matrix)
        n = len(matrix[0])
        if m == n == 0:
            return 0
        
        # 初始化dp数组
        dp = [[0] * n for _ in range(m)]
        
        # 初始化第0行和第0列
        for i in range(m):
            if matrix[i][0] == "1":
                dp[i][0] = 1
        for j in range(n):
            if matrix[0][j] == "1":
                dp[0][j] = 1
        
        # 遍历填充dp数组
        for i in range(1, m):
            for j in range(1, n):
                if matrix[i][j] == "1":
                    dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
                    
        # 返回dp数组中最大值的平方
        return max([max(i) for i in dp]) ** 2