2 Examples

2.1 Fibonacci sequence

A naive implementation of a function finding the nth member of the Fibonacci sequence, based directly on the mathematical definition, performs much redundant work. Here is that implementation:

The following is wikicode , a proposed pseudocode for use in many articles:

function fib(n) if n = 0 or n = 1 return n else return fib(n − 1) + fib(n − 2)

Notice that if we call, say, fib(5), we produce a call tree that calls the function on the same value many different times:

1. fib(5)
2. fib(4) + fib(3)
3. (fib(3) + fib(2)) + (fib(2) + fib(1))
4. ((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))
5. (((fib(1) + fib(0)) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

In particular, fib(2) was calculated twice from scratch. In larger examples, many more values of fib, or subproblems, are recalculated, leading to an exponential time ( O(2ⁿ)) algorithm.

Now, suppose we have a simple map object, m, which maps each value of fib that has already been calculated to its result, and we modify our function to use it and update it. The resulting function requires only O(n) time instead of O(2ⁿ):

var m := map(0 → 0, 1 → 1) function fib(n) if n not in keys(m) m[n] := fib(n − 1) + fib(n − 2) return m[n]

This technique of saving values that have already been calculated is called memoization; this is the top-down approach, since we first break the problem into subproblems and then calculate and store values. In this case, we can also reduce the function from using linear (O(n)) space to using constant space by changing our function to use a bottom-up approach which calculates smaller values of fib first, then build larger values from them:

function fib(n) var previousFib := 0, currentFib := 1 repeat n − 1 times var newFib := previousFib + currentFib previousFib := currentFib currentFib := newFib return currentFib

In both these examples, we only calculate fib(2) one time, and then use it to calculate both fib(4) and fib(3), instead of computing it every time either of them is evaluated.

2.2 Checkerboard

Lets say you had an checkerboard with n * n squares on it. Along with this checkerboard you get a cost-function c(i, j) which returns a cost associated with square i,j (i being the rank, j being the column). For instance (on a 5 * 5 checkerboard) ,

|---|---|---|---|---| 5 | 6 | 7 | 4 | 7 | 8 | |---|---|---|---|---| 4 | 7 | 6 | 1 | 1 | 4 | |---|---|---|---|---| 3 | 3 | 5 | 7 | 8 | 2 | |---|---|---|---|---| 2 | 2 | 6 | 7 | 0 | 2 | |---|---|---|---|---| 1 | 7 | 3 | 5 | 6 | 1 | |---|---|---|---|---| 1 2 3 4 5

Thus c(1, 3) = 5

Let's say you had a checker that could start at any square on the first rank and you wanted to know the shortest path (sum of the costs of the visited squares are at a minimum) to get to the last rank, assuming the checker could move only forward or diagonally left or right forward. That is, a checker on 1,3 can move to 2,2 2,3 or 2,4

|---|---|---|---|---| 5 | | | | | | |---|---|---|---|---| 4 | | | | | | |---|---|---|---|---| 3 | | | | | | |---|---|---|---|---| 2 | | x | x | x | | |---|---|---|---|---| 1 | | | O | | | |---|---|---|---|---| 1 2 3 4 5

This problem exhibits optimal substructure. I.e. the solution to the entire problem relies on solutions to subproblems. Let's define a function q(i, j) as

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

If we can find the values of this function for all the the squares at rank n, we pick the minimum and follow that path backwards to get the shortest path.

It's easy to see that q(i, j) is equal to the minimum cost to get to any of the three squares below it (since that's the only squares that can reach it) plus c(i, j). For instance:

|---|---|---|---|---| 5 | | | | | | |---|---|---|---|---| 4 | | | A | | | |---|---|---|---|---| 3 | | B | C | D | | |---|---|---|---|---| 2 | | | | | | |---|---|---|---|---| 1 | | | | | | |---|---|---|---|---| 1 2 3 4 5

Now, let's define q(i, j) in little more general terms:

This equation is pretty straightforward. The first line is simply there to make the recursive property simpler (when dealing with the edges, so we only need one recursion). The second line says what happens in the first rank, so we have something to start with. The third line, the recursion, is the important part. It is basically the same as the A,B,C,D example. From this definition we can make a straight-forward recursive code for q(i, j). In the following pseudocode, n is the size of the board, c(i, j) is the cost-function, and min() returns the minimum of a number of values:

function minCost(i, j) if j = 0 or j = n + 1 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)

It should be noted that this function just computes the path-cost, not the actual path. We'll get to the path soon. This, like the Fibonacci-numbers example, is horribly slow since it spends mountains of time recomputing the same shortest paths over and over. However, we can compute it much faster in a bottom up-fashion if we use a two-dimensional array q[i, j] instead of a function. Why do we do that? Simply because when using a function we recompute the same path over and over, and we can choose what values to compute first.

We also need to know what actual path is. The path problem we can solve using another array p[i, j], a predecessor array. This array basically says where path comes from. Consider the following code:

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] < min minIndex := i min := q[n, i] printPath(n, minIndex) } function printPath(y, x) { print(x) print("<-") if y = 2 print(x + p[y, x]) else printPath(y-1, x + p[y, x]) }

3 Algorithms that use dynamic programming

• the Cocke-Younger-Kasami (CYK) algorithm which determines whether and how a given string can be generated by a given context-free grammar;
• the use of transposition tables and refutation table s in computer chess;
• the Viterbi algorithm;
• the Needleman-Wunsch and other sequence alignment algorithms used in bioinformatics;
• Floyd's All-Pairs shortest path algorithm.

4 External links

• Ohio State University: CIS 680: class notes on dynamic programming, by Eitan M. Gurari

Optimization algorithms

<Hide>