leetcode：221. Maximum square [essence of DP state transition]

analysis

dp[i][j] Said to (i, j) Is the largest square side length in the lower right corner
The first row and the first column are special
Other words need to consider the essence formula ：
dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
It's the essence of the world

ac code

class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        ans = 0
        # dp[i][j] Said to (i, j) It is the largest collection in the lower right corner 1 Square area 
        m, n = len(matrix), len(matrix[0])
        dp = [[0] * n for _ in range(m)]
        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:
                        #  quintessence 
                        dp[i][j] = min(dp[i - 1][j - 1], dp[i - 1][j], dp[i][j - 1]) + 1
                    ans = max(ans, dp[i][j] * dp[i][j])
        
        return ans

summary

dp tricks
About finding one that's all 1 The largest square of