The largest square of leetcode (violence solving and dynamic programming solving)

subject

In a '0' and '1' In the two-dimensional matrix , Found contains only '1' The largest square of , And return its area .

Example 1：

Input ：matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output ：4
Example 2：

Input ：matrix = [["0","1"],["1","0"]]
Output ：1
Example 3：

Input ：matrix = [["0"]]
Output ：0
 

Tips ：

m == matrix.length
n == matrix[i].length
1 <= m, n <= 300
matrix[i][j] by '0' or '1'

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/maximal-square
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

Ideas

1. Violent solution         

         I didn't think of dynamic planning at first , Only thought of violent solution ： Is to sweep each grid in turn , See whether it satisfies the largest square formed by the upper left corner of the square .

#  Violence solution ： As far as possible , Sweep the whole rectangle one by one 
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])  # m That's ok n Column 
        max_len = min(m, n)  #  The largest side of a square is m,n The lesser of the values 
        for cur_len in range(max_len, -1, -1):  #  The side length of the current square 
            i = 0
            while i <= m - cur_len:  #  Vertical movement 
                j = 0
                next_i_len = cur_len
                while j <= n - cur_len:  #  Horizontal movement 
                    next_j_len = 1
                    cur_square = matrix[i:i + cur_len]  #  Current square 
                    for row_index in range(cur_len):
                        row = cur_square[row_index]
                        cur_row = row[j:j + cur_len]  #  Each row of the current square 
                        flag = 0  #  Used to determine whether to exit the current outer loop (i Layer of )
                        for k in range(cur_len - 1, -1, -1):
                            if cur_row[k] == '0':  #  Start with the last number in each line , As long as it equals 0, It cannot form the largest square at present 
                                next_j_len = max(next_j_len, k + 1)  #  Calculate the increment of the next horizontal displacement , Instead of just increasing each time 1, This saves a lot of time 
                                flag = 1
                                break  #  Because it cannot form the largest square at present , So just jump out of the loop (j Layer of )
                        if flag:
                            next_i_len = min(next_i_len, row_index + 1)  #  Calculate the vertical movement increment , Instead of only increasing each time 1, This saves a lot of time 
                            break  #  Because there is 0 appear , So also jump out i Layer cycle 
                    else:  #  If the current squares are all made of 1 Composed of , Will not be from the top for Cycle by break Jump out of   Then the current square is the largest square , direct return that will do 
                        print(f' The longest side :{cur_len}')
                        return cur_len ** 2

                    print(f'{next_i_len}*' * 100)
                    j += next_j_len  #  Horizontal movement 
                i += next_i_len  #  Vertical movement 

2. Dynamic programming

        Later, after reading the solution , It can be solved by dynamic programming , What is different from the above is , Here, choose a point as the vertex at the bottom right corner of the square , Then record the side of the largest square that can be formed at this point , And its value and whether it is 0 of ; At the same time with its left , The upper edge is related to the value of the point in the upper left corner , The specific state transition equation is as follows ：

#  hypothesis dp[i][j] Expressed in (i,j) Is the side length of the largest square in the lower right corner 
#  be dp[i][j] The value of is from its left , The values of the upper and upper left corners are jointly determined 

 be dp[i][j] There may be two situations in determining the value of ：
    1.matrix[i][j]=0, be dp[i][j] Directly equal to 0
    2.matrix[i][j]!=0, Compare the left , The value of the upper and upper left corner ,dp[i][j]=min(dp[i-1][j],dp[i][j-1],d[i-1][j-1])+1

#  Dynamic programming solution 
class Solution:
    def maximalSquare(self, matrix: List[List[str]]) -> int:
        m, n = len(matrix), len(matrix[0])
        dp = [[0 for j in range(n)] for i in range(m)]  #  Initialize a dp Array 
        dp[0] = [int(i) for i in matrix[0]]  #  to update dp The value of the first line , and matrix The value of the first line in is the same 
        max_len = max(dp[0])  #  Record longest edge 
        if m > 1:
            for i in range(m):
                dp[i][0] = int(matrix[i][0])  #  to update dp The value of the first column , and matrix The value of the first column in is the same 
            dp[1][0] = int(matrix[1][0])
            max_len = max(max_len, dp[1][0])
            for i in range(1, m):
                for j in range(1, n):
                    if matrix[i][j] == '0':
                        dp[i][j] = 0
                    else:
                        dp[i][j] = min(int(dp[i - 1][j]), int(dp[i][j - 1]), int(dp[i - 1][j - 1])) + 1
                    max_len = max(max_len, dp[i][j])
        return max_len ** 2

Through screenshots

  Synchronous update in personal blog system ：LeetCode The largest square ( Violent solution and dynamic programming solution )