Editing Dynamic programming (section)

=== Checkerboard ===
{{unreferenced section|date=May 2013}}
Consider a [[checkerboard]] with ''n'' × ''n'' squares and a cost function <code>c(i, j)</code> which returns a cost associated with square <code>(i,j)</code> (<code>''i''</code> being the row, <code>''j''</code> being the column). For instance (on a 5 × 5 checkerboard),

{| class="wikitable" style="text-align:center"
|-
! 5
| 6 || 7 || 4 || 7 || 8
|-
! 4
| 7 || 6 || 1 || 1 || 4
|-
! 3
| 3 || 5 || 7 || 8 || 2
|-
! 2
| – || 6 || 7 || 0 || –
|-
! 1
| – || – || '''5''' || – || –
|-
!width="15"| !! style="width:15px;"|1 !! style="width:15px;"|2 !! style="width:15px;"|3 !! style="width:15px;"|4 !! style="width:15px;"|5
|}
Thus <code>c(1, 3) = 5</code>

Let us say there was a checker that could start at any square on the first rank (i.e., row) and you wanted to know the shortest path (the sum of the minimum costs at each visited rank) to get to the last rank; assuming the checker could move only diagonally left forward, diagonally right forward, or straight forward. That is, a checker on <code>(1,3)</code> can move to <code>(2,2)</code>, <code>(2,3)</code> or <code>(2,4)</code>.
{| class="wikitable" style="text-align:center"
|-
! 5
|  ||  ||  ||  ||
|-
! 4
|  ||  ||  ||  ||
|-
! 3
|  ||  ||  ||  ||
|-
! 2
|  || x  || x || x ||
|-
! 1
|  ||  || o ||  ||
|-
!width="15"| !! style="width:15px;"|1 !! style="width:15px;"|2 !! style="width:15px;"|3 !! style="width:15px;"|4 !! style="width:15px;"|5
|}

This problem exhibits '''optimal substructure'''. That is, the solution to the entire problem relies on solutions to subproblems. Let us define a function <code>q(i, j)</code> as

:''q''(''i'', ''j'') = the minimum cost to reach square (''i'', ''j'').

Starting at rank <code>n</code> and descending to rank <code>1</code>, we compute the value of this function for all the squares at each successive rank. Picking the square that holds the minimum value at each rank gives us the shortest path between rank <code>n</code> and rank <code>1</code>.

The function <code>q(i, j)</code> is equal to the minimum cost to get to any of the three squares below it (since those are the only squares that can reach it) plus <code>c(i, j)</code>. For instance:

{| class="wikitable" style="text-align:center"
|-
! 5
|  ||  ||  ||  ||
|-
! 4
|  ||  || A  ||  ||
|-
! 3
|  || B || C || D ||
|-
! 2
|  ||  ||  ||  ||
|-
! 1
|  ||  ||  ||  ||
|-
!width="15"| !! style="width:15px;"|1 !! style="width:15px;"|2 !! style="width:15px;"|3 !! style="width:15px;"|4 !! style="width:15px;"|5
|}

: <math>q(A) = \min(q(B),q(C),q(D))+c(A) \, </math>

Now, let us define <code>q(i, j)</code> in somewhat more general terms:

: <math>q(i,j)=\begin{cases} \infty & j < 1 \text{ or }j > n \\ c(i, j) & i = 1 \\ \min(q(i-1, j-1), q(i-1, j), q(i-1, j+1)) + c(i,j) & \text{otherwise.}\end{cases}</math>

The first line of this equation deals with a board modeled as squares indexed on <code>1</code> at the lowest bound and <code>n</code> at the highest bound. The second line specifies what happens at the first rank; providing a base case. The third line, the recursion, is the important part. It represents the <code>A,B,C,D</code> terms in the example. From this definition we can derive straightforward recursive code for <code>q(i,&nbsp;j)</code>. In the following pseudocode, <code>n</code> is the size of the board, <code>c(i, j)</code> is the cost function, and <code>min()</code> returns the minimum of a number of values:

 '''function''' minCost(i, j)
     '''if''' j &lt; 1 '''or''' j > n
         '''return''' infinity
     '''else if''' i = 1
         '''return''' c(i, j)
     '''else'''
         '''return''' '''min'''( minCost(i-1, j-1), minCost(i-1, j), minCost(i-1, j+1) ) + c(i, j)

This function only computes the path cost, not the actual path. We discuss the actual path below. This, like the Fibonacci-numbers example, is horribly slow because it too exhibits the '''overlapping sub-problems''' attribute. That is, it recomputes the same path costs over and over. However, we can compute it much faster in a bottom-up fashion if we store path costs in a two-dimensional array <code>q[i, j]</code> rather than using a function. This avoids recomputation; all the values needed for array <code>q[i, j]</code> are computed ahead of time only once. Precomputed values for <code>(i,j)</code> are simply looked up whenever needed.

We also need to know what the actual shortest path is. To do this, we use another array <code>p[i, j]</code>; a ''predecessor array''. This array records the path to any square <code>s</code>. The predecessor of <code>s</code> is modeled as an offset relative to the index (in <code>q[i, j]</code>) of the precomputed path cost of <code>s</code>. To reconstruct the complete path, we lookup the predecessor of <code>s</code>, then the predecessor of that square, then the predecessor of that square, and so on recursively, until we reach the starting square. Consider the following pseudocode:

 '''function''' computeShortestPathArrays()
     '''for''' x '''from''' 1 '''to''' n
         q[1, x] := c(1, x)
     '''for''' y '''from''' 1 '''to''' n
         q[y, 0]     := infinity
         q[y, n + 1] := infinity
     '''for''' y '''from''' 2 '''to''' n
         '''for''' x '''from''' 1 '''to''' n
             m := min(q[y-1, x-1], q[y-1, x], q[y-1, x+1])
             q[y, x] := m + c(y, x)
             '''if''' m = q[y-1, x-1]
                 p[y, x] := -1
             '''else if''' m = q[y-1, x]
                 p[y, x] :=  0
             '''else'''
                 p[y, x] :=  1

Now the rest is a simple matter of finding the minimum and printing it.

 '''function''' computeShortestPath()
     computeShortestPathArrays()
     minIndex := 1
     min := q[n, 1]
     '''for''' i '''from''' 2 '''to''' n
         '''if''' q[n, i] &lt; min
             minIndex := i
             min := q[n, i]
     printPath(n, minIndex)

 '''function''' printPath(y, x)
     '''print'''(x)
     '''print'''("&lt;-")
     '''if''' y = 2
         '''print'''(x + p[y, x])
     '''else'''
         printPath(y-1, x + p[y, x])