Editing Dynamic programming (section)

=== A type of balanced 0–1 matrix ===
{{unreferenced section|date=May 2013}}
Consider the problem of assigning values, either zero or one, to the positions of an {{math|<var>n</var> &times; <var>n</var>}} matrix, with {{math|<var>n</var>}} even, so that each row and each column contains exactly {{math|<var>n</var> / 2}} zeros and {{math|<var>n</var> / 2}} ones. We ask how many different assignments there are for a given <math>n</math>. For example, when {{math|<var>n</var> {{=}} 4}}, five possible solutions are

:<math>\begin{bmatrix}
0 & 1 & 0 & 1 \\
1 & 0 & 1 & 0 \\
0 & 1 & 0 & 1 \\
1 & 0 & 1 & 0
\end{bmatrix} \text{ and } \begin{bmatrix}
0 & 0 & 1 & 1 \\
0 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
1 & 1 & 0 & 0
\end{bmatrix} \text{ and } \begin{bmatrix}
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1
\end{bmatrix} \text{ and } \begin{bmatrix}
1 & 0 & 0 & 1 \\
0 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 0 & 1
\end{bmatrix} \text{ and } \begin{bmatrix}
1 & 1 & 0 & 0 \\
1 & 1 & 0 & 0 \\
0 & 0 & 1 & 1 \\
0 & 0 & 1 & 1
\end{bmatrix}.</math>

There are at least three possible approaches: [[Brute-force search|brute force]], [[backtracking]], and dynamic programming.

Brute force consists of checking all assignments of zeros and ones and counting those that have balanced rows and columns ({{math|<var>n</var> / 2}} zeros and {{math|<var>n</var> / 2}} ones). As there are <math>2^{n^2}</math> possible assignments and <math>\tbinom{n}{n/2}^n</math> sensible assignments, this strategy is not practical except maybe up to <math>n=6</math>.

Backtracking for this problem consists of choosing some order of the matrix elements and recursively placing ones or zeros, while checking that in every row and column the number of elements that have not been assigned plus the number of ones or zeros are both at least {{math|<var>n</var> / 2}}. While more sophisticated than brute force, this approach will visit every solution once, making it impractical for {{math|<var>n</var>}} larger than six, since the number of solutions is already 116,963,796,250 for {{math|<var>n</var>}}&nbsp;=&nbsp;8, as we shall see.

Dynamic programming makes it possible to count the number of solutions without visiting them all. Imagine backtracking values for the first row – what information would we require about the remaining rows, in order to be able to accurately count the solutions obtained for each first row value? We consider {{math|<var>k</var> &times; <var>n</var>}} boards, where {{math|1 &le; <var>k</var> &le; <var>n</var>}}, whose <math>k</math> rows contain <math>n/2</math> zeros and <math>n/2</math> ones. The function ''f'' to which [[memoization]] is applied maps vectors of ''n'' pairs of integers to the number of admissible boards (solutions). There is one pair for each column, and its two components indicate respectively the number of zeros and ones that have yet to be placed in that column. We seek the value of <math> f((n/2, n/2), (n/2, n/2), \ldots (n/2, n/2)) </math> (<math>n</math> arguments or one vector of <math>n</math> elements). The process of subproblem creation involves iterating over every one of  <math>\tbinom{n}{n/2}</math> possible assignments for the top row of the board, and going through every column, subtracting one from the appropriate element of the pair for that column, depending on whether the assignment for the top row contained a zero or a one at that position. If any one of the results is negative, then the assignment is invalid and does not contribute to the set of solutions (recursion stops). Otherwise, we have an assignment for the top row of the {{math|<var>k</var> &times; <var>n</var>}} board and recursively compute the number of solutions to the remaining {{math|(<var>k</var> &minus; 1) &times; <var>n</var>}} board, adding the numbers of solutions for every admissible assignment of the top row and returning the sum, which is being memoized. The base case is the trivial subproblem, which occurs for a {{math|1 &times; <var>n</var>}} board. The number of solutions for this board is either zero or one, depending on whether the vector is a permutation of {{math|<var>n</var> / 2}} <math>(0, 1)</math> and {{math|<var>n</var> / 2}} <math>(1, 0)</math> pairs or not.

For example, in the first two boards shown above the sequences of vectors would be
<pre>
((2, 2) (2, 2) (2, 2) (2, 2))       ((2, 2) (2, 2) (2, 2) (2, 2))     k = 4
  0      1      0      1              0      0      1      1

((1, 2) (2, 1) (1, 2) (2, 1))       ((1, 2) (1, 2) (2, 1) (2, 1))     k = 3
  1      0      1      0              0      0      1      1

((1, 1) (1, 1) (1, 1) (1, 1))       ((0, 2) (0, 2) (2, 0) (2, 0))     k = 2
  0      1      0      1              1      1      0      0

((0, 1) (1, 0) (0, 1) (1, 0))       ((0, 1) (0, 1) (1, 0) (1, 0))     k = 1
  1      0      1      0              1      1      0      0

((0, 0) (0, 0) (0, 0) (0, 0))       ((0, 0) (0, 0), (0, 0) (0, 0))
</pre>

The number of solutions {{OEIS|id=A058527}} is

:<math> 1,\, 2,\, 90,\, 297200,\, 116963796250,\, 6736218287430460752, \ldots </math>

Links to the MAPLE implementation of the dynamic programming approach may be found among the [[#External links|external links]].