30daychallenge (27) | Maximal Square

 Given a 2D binary matrix filled with 0's and 1's, find the largest square containing only 1's and return its area.

Example:

Input: 

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Output: 4

Gần như bài hôm qua, vẽ cái bảng ra là bạn sẽ thấy công thức truy hồi:

dp[i][j] = matrix[i][j] = 0 ->  min(dp[i-1][j],[dp[i][j-1],dp[i-1][j-1] + 1 | 0

Hãy tưởng tượng nếu đứng ở một vị trí bất kỳ [i][j], nếu có một hình vuông với góc trái trên cùng là [i][j] thì ba cái [i+1][j], [i][j+1], [i+1][j+1] phải đều bằng 1 và bản thân [i][j] cũng phải bằng 1. Lý do ta lấy min vì ta muốn chắc chắn rằng cả ba cạnh này đều bằng nhau.

Khó nhất phần tìm ra công thức truy hồi thôi. Còn đây là code Java của mình, độ phức tạp là O(M*N) và độ phức tạp không gian là O(N) như bài hôm qua.
Hết rồi. Hẹn gặp lại bạn ngày mai. Cảm ơn !