Maximum Square

https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/531/week-4/3312/

DP

以当前position (i,j) 作为点, dp[i][j] 代表以i，j为顶点最大的正方形长度

recurrence relation

$$dp[i][j] = min(dp[i-1][j-1], dp[i][j-1], dp[i-1][j]) + 1, when, matrix[i][j] = 1$$

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

把上面的code简化一下成为

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        length = 0
        m = len(matrix)
        if m == 0:
            return 0
        n = len(matrix[0])
        dp = [n*[0] for _ in range(m)]
        
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "1":
                    if i >= 1 and j >=1:
                        dp[i][j] = min([dp[i][j-1],dp[i-1][j],dp[i-1][j-1]])+1
                    else:
                        dp[i][j] =1
                    length = max(length,dp[i][j])
        return length**2