I study DP on classical problems. There is such a task:
Given an NxM matrix consisting only of zeros and ones, you need to find the area of ​​the largest square submatrix consisting only of units. I found the formula in Google:

a[i][j] = min (a[i-1][j-1],a[i][j-1],a[i-1][j])+1

But unfortunately, I do not understand anything about it. The only thing I understand is that from a[i-1][j-1] ( a[i][j] is the side of a square with max. Area at which the bottom corner has coordinates i,j ) you can go to a[i][j] , but for this it is necessary that the element was equal to 1 and that to the left and above the element i,j elements were equal to 1.

  • one
    And what is DP, sorry? - VladD
  • one
    @VladD judging by the task, free abbreviation for "Dynamic Programming" - rdorn

2 answers 2

A PHP program looks like this:

 $a = [ [0,0,1,1,0,0,1,1,0,1,0], [0,0,1,1,0,0,1,1,0,1,1], [0,0,1,1,1,1,1,1,0,1,0], [0,0,0,1,1,1,1,1,0,1,1], [0,0,1,1,1,1,1,1,0,1,0], [0,0,0,1,1,1,1,1,0,1,1], [0,0,1,1,1,1,1,1,0,1,0], [0,0,1,1,0,0,1,1,0,1,0], [0,0,1,1,0,0,1,1,0,1,1], [0,0,1,1,0,0,1,1,0,1,1] ]; foreach($a as $str){ print "<br>"; foreach($str as $item) print $item; } print "<br>"; $m = count($a); $n = count($a[0]); $side = 0; for($i = 0; $i < $m; $i++){ for($j = 0; $j < $n; $j++){ if ($i*$j == 0) continue; if($a[$i][$j] == 1) $a[$i][$j] = min($a[$i][$j-1], $a[$i-1][$j], $a[$i-1][$j-1]) + 1; if ($a[$i][$j]>$side) $side=$a[$i][$j]; } } foreach($a as $str){ print "<br>"; foreach($str as $item) print $item; } printf("<br><br>Площадь максимального квадрата равна %d", $side*$side);

The conclusion is:

 00110011010
 00110011011
 00111111010
 00011111011
 00111111010
 00011111011
 00111111010
 00110011010
 00110011011
 00110011011

 00110011010
 00120012011
 00121112010
 00012222011
 00112333010
 00012344011
 00112345010
 00120012010
 00120012011
 00120012012

 The maximum square is 25

It is easy to see that after the program is executed, the original matrix contains as elements the maximum side filled with matrix units with the corresponding lower right corner (the maximum is calculated from the already transformed matrix elements).
How does this happen?

For the left column and the top row, these elements already match, so they are skipped in processing.

In other cases, the current element of the matrix increases, provided that it is equal to 1. At the same time, the minimum of the three elements bordering the current element on the left, top and left-top is taken as the base for the increase.
A simple analysis of the pictures shows that this formula is correct.

PS Let's conduct this analysis for the next current state of the matrix. Square matrix

When forming the next element (which is still equal to 1), the following facts are used:

  1. The next element is equal to one (if it would be zero, then the side of the square, too)
  2. The maximum square on the left-top of the next element (black square) has side 3, therefore the maximum side of the new square cannot be greater than 4. In general, this restriction is equal to the length of the side of the black square plus 1.
  3. Under the conditions of point 2, the length of the filled green bar is equal to the side of the green square and is 3, therefore the maximum side of the new square cannot be greater than 4. In general, this restriction is equal to the side of the green square plus 1.
  4. Under the conditions of paragraph 2, the length of the filled red strip is equal to the side of the red square and equal to 3, therefore the maximum side of the new square cannot be greater than 4. In general, this restriction is equal to the side of the red square plus 1.
  5. Since nn. 1-4 exhaust the list of possible constraints, then, with step 1, the maximum length of the side of the filled square with the lower right corner on the next element of the matrix is ​​equal to the minimum of this value in black, green and red squares, increased by one.

    The answer is contained in the formula itself. In effect, you convert a matrix that contains only 0 and 1 to a matrix that contains the lengths of the sides of the squares.

    Calculation rule:

     if (a[i][j] != 0) { a[i][j] = min (a[i-1][j-1],a[i][j-1],a[i-1][j])+1 }

    From the rule it is clear that if there is at least one zero element, then the value of the element will not change.

    To begin with, take a 2 * 2 matrix filled with only 1 and go through its cells according to the above rule. the values ​​of cells outside the matrix will be considered equal to 0. We obtain:
    1 1 => 1 1
    1 1 => 1 2

    it is not difficult to notice, the value of the lower right corner of the matrix has changed to 2.

    For a 3 * 3 matrix, the conversion will look like this:
    1 1 1 => 1 1 1
    1 1 1 => 1 2 2
    1 1 1 => 1 2 3

    After transforming an arbitrary rectangular matrix with 0 and 1 in this way, the solution of the problem is reduced to finding the maximum element in the transformed matrix.

    Upd.

    At the request of the workers I will try to show the conclusion of this formula. Immediately I warn you that I thoroughly forgot the correct mathematical terminology, therefore, "on the fingers."

    Let us take as a basis the statement that the element of matrix A equal to 1 is a square submatrix of size 1 * 1 and all its elements are different from 0. The element of the matrix equal to 0 is an empty submatrix, all elements of which are equal to 0. Since in both cases, the submatrices contain a single element, both statements are true.

    The main diagonal consists of the elements a [i] [i] (i = 1..n)

    We agree that A '[k] [k] = k if all elements of the submatrix A' of size k are different from 0 .

    And one more statement: In a square matrix of size N, we can distinguish a square submatrix of size N-1 in four different ways (by the number of angles).

    From all the above, it follows that if A [i] [j] = k> 0, then in the matrix A there exists a square submatrix A 'of size k, all elements of which are different from 0, while the element A [i] [j] itself is an element of A '[k] [k] of this submatrix.

    Then k = min (A [i-1] [j-1], A [i-1] [j], A [i] [j-1]) will mean the minimum size of three adjacent to A [i] [j ] square submatrices all elements of which are different from 0. If the element A [i] [j] itself is different from 0, then there exists a submatrix of size k + 1 , all of whose elements are also different from 0.

    Something like this. I hope not distorted too much. Terminology.

    • But how can this formula be derived or proved? Because for me the most important thing is how to get the formula, it's not difficult to write a program. Why do we take a minimum and how do problems a [i] [j-1], a [i-1] [j] help solve the problem a [i] [j]? - moskalenco_a
    • @AndreyMoskalenko added - rdorn pm