Mô phỏng thuật toán Hình vuông toàn 1 lớn nhất

Maximal Square · Nhóm: Quy hoạch động

Hình vuông toàn 1 lớn nhất (Maximal Square), nhóm Quy hoạch động.

Mã Python

def maximal_square(matrix):
    R, C = len(matrix), len(matrix[0])
    dp = [[0]*C for _ in range(R)]
    best = 0
    for i in range(R):
        for j in range(C):
            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
            else:
                dp[i][j] = 0
            best = max(best, dp[i][j])
    return best * best

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.