Dynamic programming is not a specific algorithm, but rather a programming technique (like recursion). It is best described as creating solutions to large problems by combining solutions to smaller problems. On some problems, applying dynamic programming can change the efficiency from exponential to polynomial.

Consider the problem of computing the Nth Fibonacci number F(N). The Fibonacci sequence starts 1, 1, 2, 3, 5, 8, ..., with each number being the sum of the previous two. So a simple recursive implementation might look like this:

function fib(n : integer) : integer; begin if n <= 2 then fib := 1 else fib := fib(n - 2) + fib(n - 1); end;

That is all well and good, but how efficienct is it? It turns out to
take time proportional to the *answer*, which is in fact
exponential time (`O(s ^{n})`, where

The key observation is that the recursive function is a true
function in the mathematical sense: it has no side effects, and the
output depends only on the input `n`. This means that we don't
have to start by asking for the Nth Fibonacci number and work
downwards, but can start with the first one and work upwards. Here is
the code (`arr` is an array that is assumed to be big enough):

function fib(n : integer) : integer; var i : integer; begin arr[1] := 1; arr[2] := 1; for i := 3 to n do arr[i] := arr[i - 1] + arr[i - 2]; fib := arr[n]; end;

This computes the smaller problems of finding F(1), F(2), F(3) and so on, and combines these to produce the answers to the bigger problem of finding F(n).

Identifying problems that can be solving with dynamic programming is something that comes with practice. To begin with, the following procedure will help you see the dynamic programming solutions.

- Write a recursive solution to the problem.
- Modify the recursive function until it becomes a mathematical function. That is, it must have no side effect and the answer must depend only on the parameters. It may also depend on global variables but these must be static input data, not variables that change over the course of the program. If you cannot modify the recursion to do this, then it is possible that the problem cannot be solved with dynamic programming.
- Try to reduce the number of parameters as much as possible. If there are parameters that are the same for the entire program, make them global variables. If there are parameters that can be calculated from other parameters, remove them.
- Create an array (possibly multi-dimensional) whose indices correspond to the parameters of the recursive function. The array should be able to hold the answer for every possible call to the function.
- Work out what dependencies are used in the recursive function. In the Fibonacci example, F(n) depends on F(n - 1) and F(n - 2).
- Write nested loops to loop over all possible inputs to the function, up to the inputs you actually want. Organise the loops so that dependencies are satisfied (e.g. so that F(n - 1) and F(n - 2) are computed before they are needed to compute F(n)). For each set of inputs, compute the output and store it into the array. Do not call the recursive function but rather get the answer from the array.

Sometimes the parameter space (the set of all legal input parameters) is too large to store in an array. This will usually happen if there are several parameters. To get around this, it is sometimes possible to get around this by only storing a subset of the parameter space (this depends on the problem). To return to the Fibonacci problem, we see that we only need to keep the last two Fibonacci numbers, as the previous ones are never used again. The modified code is:

function fib(n : integer) : integer; var f1, f2, cur, i : integer; begin f1 := 1; f2 := 1; cur := 1; for i := 3 to n do begin f1 := f2; f2 := cur; cur := f1 + f2; end; fib := cur; end;

More generally, the array will have multiple dimensions, and sometimes only one or two "rows" of the array are needed at one time. These cases can be identitied from the dependencies: in the Fibonacci example, F(n) depends only on the previous two elements, so those are all that need to be kept.

Sometimes the dependencies in problems are rather complicated, and this can make the ordering of the loops rather tricky. This often arises in problems involving graphs, where the dependencies are edges in the graph. Another problem with writing loops is that it is sometimes more efficient to avoid solving sub-problems that are never actually used to solve the main problem.

Both of these problems are addressed by a technique known as
*memoisation* or *caching*. It is equivalent to dynamic
programming, but I find it to be more work and generally only implement
it when these problems arise. The basic approach is to stop after step
4 in the process above, leaving you with a recursive function and an
array for holding the outputs. Initially tag all the array elements to
indicate that they have not been computed (e.g. by storing -1). Then
modify the recursive function to return the array value if it has
already been computed, and to do the work otherwise. The array thus
acts as a *cache* of results that have already been computed.
Reusing the Fibonacci example:

var cache : array[1..MAXN] of longint; procedure initialise; begin fill cache with -1's, indicating that the value isn't known fillchar(cache, sizeof(cache), 255); if we initialise the first 2 here, it simplies the real function cache[1] := 1; cache[2] := 1; end; function fib(n : integer) : integer; begin if (cache[n] = -1) then cache[n] := fib(n - 1) + fib(n - 2); fib := cache[n]; end;

Last updated Sat May 31 19:48:29.0000000000 2008. Copyright Bruce Merry (bmerry '@' gmail dot. com).