This section gives a short introduction to dynamic programming. Readers not interested in the algorithm underlying the alignment routines should proceed to the next section.

Dynamic programming is a standard algorithmic technique in computer
science and is particularily useful for problems such as sequence
alignment. Intuitively, dynamic programming works *bottom to
top* computing solutions to subproblems and storing them in a
table. In this way, every subproblem is solved exactly once and when
a subproblem is re-encountered the answer need not be recomputed.

There are two qualities a problem must possess for dynamic programming
to be applicable:

(1) Optimal substructure. The optimal solution to the problem must
contain within it optimal solutions to subproblems.

(2) Overlapping subproblems. The number of distinct subproblems is
small.^{19.1}

It is not hard to see that most sequence alignment problems exhibit both of these behaviours. We will proceed by giving a simple example of how dynamic programming works.