力扣 221. 最大正方形

动态规划

def maximalSquare(matrix):
    # 动态规划
    m, n = len(matrix), len(matrix[0])
    dp = [[0] * n for _ in range(m)]
    ret = 0
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == "1":
                if i == 0 or j == 0:
                    dp[i][j] = 1
                else:
                    dp[i][j] = min(dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]) + 1
            ret = max(ret, dp[i][j])
    return ret ** 2