2.3. Dynamic programming

What is dynamic programming?

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.

An example

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(sn), where s is the golden ratio). This example is usually used to show the pitfalls of recursion, but also provides a simple example of converting a problem to dynamic programming.

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).

The general approach

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.

  1. Write a recursive solution to the problem.
  2. 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.
  3. 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.
  4. 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.
  5. 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).
  6. 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.

Saving memory

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.

Memoisation

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;
[Prev] [Next] [Up]

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