Problem contest with matrix and DP 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 $n\times n$ filled with 1's or 0's, like this:

$$\begin{bmatrix} 1 &amp;1 &amp;1 &amp;0\\ 1 &amp;1 &amp;1 &amp;1\\ 0 &amp;0 &amp;1 &amp;0\\ 1 &amp;1 &amp;1 &amp;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 &amp; 1\\
1 &amp;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.
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.