Problem Detail: I found this problem while I was reading an ACM problem and it is about dynamic programming. The problem says that you have a square matrix $ntimes n$ filled with 1’s or 0’s, like this:
$$begin{bmatrix} 1 &1 &1 &0 1 &1 &1 &1 0 &0 &1 &0 1 &1 &1 &1 end{bmatrix}$$
Now you have to find the biggest square matrix inside the original matrix which is filled with only 1’s. In my example, take the matrix of $((1,1)$ to $(2,2)$ $$ begin{bmatrix} 1 & 1 1 &1 end{bmatrix} $$ But, we might have to deal with matrices of size 1000X1000 as well. So the algorithm should be efficient and use DP, although I don’t know if there is other solution. My Teacher told me that it can be done by Dynamic Programming. But I didn’t understand his method.
Asked By : jonaprieto
Answered By : Aryabhata
An $O(n^2)$ algorithm is possible. Let $A$ be the given matrix. You compute the side of largest square with the bottom right corner at $(i,j)$, say $S(i,j)$ Now we can compute the side of the larger square for $(i+1, j+1)$ in terms of $S(i,j), S(i+1,j), S(i,j+1)$ as $$S(i+1,j+1) = min {S(i,j), S(i+1,j), S(i,j+1)} + 1 quad text{if}quad A[i+1,j+1] = 1$$ and $$S(i+1,j+1) = 0 text{if } A[i+1,j+1] = 0$$ There are other (complicated) $O(n^2)$ algorithms available, which also work for rectangles and can be used for this problem.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/3340
