Dynamic programming
From Academic Kids

In computer science, dynamic programming is a method for reducing the runtime of algorithms exhibiting the properties of overlapping subproblems and optimal substructure, described below.
The field was founded as a systems analysis and engineering topic which is recognized by the IEEE.
Contents 
Overview
Shortest_path_optimal_substructure.png
Optimal substructure means that optimal solutions of subproblems can be used to find the optimal solutions of the overall problem. For example, the shortest path to a goal from a vertex in a graph can be found by first computing the shortest path to the goal from all adjacent vertices, and then using this to pick the best overall path, as shown in Figure 1. In general, we can solve a problem with optimal substructure using a threestep process:
 Break the problem into smaller subproblems.
 Solve these problems optimally using this threestep process recursively.
 Use these optimal solutions to construct an optimal solution for the original problem.
The subproblems are, themselves, solved by dividing them into subsubproblems, and so on, until we reach some simple case that is easy to solve.
Fibonacci_dynamic_programming.png
To say that a problem has overlapping subproblems is to say that the same subproblems are used to solve many different larger problems. For example, in the Fibonacci sequence, F_{3} = F_{1} + F_{2} and F_{4} = F_{2} + F_{3} — computing each number involves computing F_{2}. Because both F_{3} and F_{4} are needed to compute F_{5}, a naïve approach to computing F_{5} may end up computing F_{2} twice or more. This applies whenever overlapping subproblems are present: a naïve approach may waste time recomputing optimal solutions to subproblems it has already solved.
In order to avoid this, we instead save the solutions to problems we have already solved. Then, if we need to solve the same problem later, we can retrieve and use our alreadycomputed solution. This approach is called memoization (not memorization, although this term also fits). If we are sure we won't need a particular solution anymore, we can throw it away to save space. In some cases, we can even compute the solutions to subproblems we know that we'll need in advance.
In summary, dynamic programming makes use of:
Dynamic programming usually takes one of two approaches:
 Topdown approach: The problem is broken into subproblems, and these subproblems are solved and the solutions remembered, in case they need to be solved again.
 Bottomup approach: All subproblems that might be needed are solved in advance and then used to build up solutions to larger problems.
Originally, the term dynamic programming only applied to solving certain kinds of operational problems outside the area of computer science, just as linear programming did. In this context it has no particular connection to programming at all; the name is a coincidence. The term was also used in the 1940s by Richard Bellman, an American mathematician to describe the process of solving problems where one needs to find the best decisions one after another.
Some functional programming languages, most notably Haskell, can automatically memoize the result of a function call with a particular set of arguments, in order to speed up callbyname evaluation (this mechanism is referred to as callbyneed). This is only possible for a function which has no sideeffects, which is always true in Haskell but seldom true in imperative languages.
Examples
Fibonacci sequence
A naïve implementation of a function finding the nth member of the Fibonacci sequence, based directly on the mathematical definition, performs much redundant work:
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:

fib(5)

fib(4) + fib(3)

(fib(3) + fib(2)) + (fib(2) + fib(1))

((fib(2) + fib(1)) + (fib(1) + fib(0))) + ((fib(1) + fib(0)) + fib(1))

(((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 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 exponential time:
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 topdown 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 bottomup 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.
Checkerboard
Consider a checkerboard with n × n squares and a costfunction 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 us 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. That is, the solution to the entire problem relies on solutions to subproblems. Let us 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 squares at rank n, we pick the minimum and follow that path backwards to get the shortest path.
It is 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 is 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
 <math>q(A) = \min(q(B),\;q(C),\;q(D))\;+\;c(A)<math>
Now, let us define q(i, j) in little more general terms:
 <math>q(i,j)=\left\{\begin{matrix} \infty & j = 0 \mbox{ or }j = n+1 \\ c(i, j) & i = 1 \\ \min(q(i1, j1), q(i1, j), q(i1, j+1)) + c(i,j) & \mbox{otherwise}\end{matrix}\right.<math>
This equation is pretty straightforward. The first line is simply there to make the recursive property simpler (when dealing with the edges, so we need only 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 straightforward recursive code for q(i, j). In the following pseudocode, n is the size of the board, c(i, j)
is the costfunction, 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(i1, j1), minCost(i1, j), minCost(i1, j+1) ) + c(i, j)
It should be noted that this function just computes the pathcost, not the actual path. We will get to the path soon. This, like the Fibonaccinumbers 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 upfashion if we use a twodimensional 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 the 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[y1, x1], q[y1, x], q[y1, x+1]) q[y, x] := m + c(y, x) if m = q[y1, x1] p[y, x] := 1 else if m = q[y1, 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(y1, x + p[y, x])
Algorithms that use dynamic programming
 the CockeYoungerKasami (CYK) algorithm which determines whether and how a given string can be generated by a given contextfree grammar
 the use of transposition tables and refutation tables in computer chess
 the Viterbi algorithm
 the NeedlemanWunsch and other sequence alignment algorithms used in bioinformatics
 Levenshtein distance (edit distance)
 Floyd's AllPairs shortest path algorithm
 the algorithm that optimizes the order for chain matrix multiplication
History
Mathematician Richard Bellman (1920–1984) invented dynamic programming in 1953.
External links
 David B. Wagner. Dynamic Programming (http://citeseer.ist.psu.edu/268391.html). A 1995 introductory article on dynamic programming.
 Ohio State University: CIS 680: class notes on dynamic programming (http://www.cse.ohiostate.edu/~gurari/course/cis680/cis680Ch21.html), by Eitan M. Gurari
 A Tutorial on Dynamic programming (http://mat.gsia.cmu.edu/classes/dynamic/dynamic.html)de:Dynamische Programmierung