2.7 Dynamic Programming

Dynamic programming computes the values for small subproblems and stores those values in a matrix. The stored values are then used to solve larger subproblems (without incurring the cost of recomputing the smaller subproblems) and so on until the solution to the overall problem is found. The term "dynamic programming" is a bit of a misnomer since it doesn't involve changing values over time as the word "dynamic" suggests.

This approach relies on having a data structure available to store the intermediate values as the algorithm proceeds. The data structure may require a fair amount of computer memory, but the overall speed of the algorithm often makes the memory cost worthwhile. In this section, we'll use a Perl multidimensional array, namely a simple two-dimensional matrix, to solve an approximate string matching problem.

Our algorithm will find a (shorter) pattern in a (longer) text. We'll start with a two-dimensional array, or matrix. The columns of the matrix will be associated with the (shorter) pattern, and the rows of the matrix will be associated with the (longer) text. The zeroth row and the zeroth column will be initialized to the appropriate starting values. We'll then calculate each value in the matrix by examining adjacent, already calculated values in conjunction with the characters of the pattern and the text. After the entire matrix has been filled in, we'll have the answer to our problem. That is, we'll find the position(s) in the text that most closely match the pattern, and we'll do so by simply examining the values in the last row of the matrix.