Dynamic programming

This resource is currently unmaintained. Please feel welcome to adopt it and then change this tag.

In computer science, dynamic programming is a method of solving problems exhibiting the properties of overlapping subproblems and optimal substructure that takes much less time than naïve methods.

The term was originally used in the 1940s by Richard Bellman to describe the process of solving problems where one needs to find the best decisions one after another. By 1953, he had refined it to the modern meaning. The field was founded as a systems analysis and engineering topic which is recognized by the IEEE.

The word "programming" in "dynamic programming" has no particular connection to computer programming at all. A program is, instead, the plan for action that is produced. For instance, a finalized schedule of events at an exhibition is sometimes called a program. Programming, in this sense, is finding an acceptable plan of action.

Algorithms that use dynamic programming

Many string algorithms including longest common subsequence
The Cocke–Younger–Kasami (CYK) algorithm which determines whether and how a given string can be generated by a given context-free grammar
The use of transposition tables and refutation tables in computer chess
The Viterbi algorithm (used for hidden Markov models)
The Earley algorithm (a type of chart parser)
The Needleman–Wunsch and other sequence alignment algorithms used in bioinformatics
Levenshtein distance (edit distance)
Floyd's all-pairs shortest path algorithm
Optimizing the order for chain matrix multiplication
Subset Sum algorithm
knapsack problem
The dynamic time warping algorithm for computing the global distance between two time series
The Selinger (a.k.a. System R) algorithm for relational database query optimization
De Boor algorithm for evaluating B-spline curves
Duckworth–Lewis method for resolving the problem when games of cricket are interrupted
The value iteration method for solving Markov decision processes

Guided activity: learning edit distance

Learning goals: By the end of this activity, learners should be able to (1) explain insertion, deletion, and substitution, (2) fill a small edit-distance table, (3) derive and implement the dynamic-programming recurrence, and (4) explain what a Unicode character unit means in this context.

Prerequisites

Basic strings and arrays.
Loops and two-dimensional tables.
The idea that a larger problem can be solved from smaller prefix problems.

What is the problem?

The Levenshtein distance between two strings is the minimum number of single-symbol insertions, deletions, and substitutions required to transform one string into the other. Here every edit costs one. A matching symbol costs zero.

Example: cat becomes cut with one substitution; hence the distance is 1. cat becomes cast with one insertion; its distance is also 1.

Activity 1: Work out a small case

Compare cat and cut. Create a table with one extra row and column to represent the empty prefix. The first row reads 0, 1, 2, 3; so does the first column. Work through the table one square at a time.

	∅	c	u	t
∅	0	1	2	3
c	1	0	1	2
a	2	1	1	2
t	3	2	2	1

Question: Why does the diagonal cell in row a, column u add one, whereas row c, column c adds zero?

Activity 2: Derive the recurrence

Let D(i,j) be the distance between the first i symbols of source string a and the first j symbols of target string b. Then D(i,0)=i and D(0,j)=j. For positive i and j:

D (i, j) = min {D (i - 1, j) + 1, D (i, j - 1) + 1, D (i - 1, j - 1) + [a_{i} \neq b_{j}]} .

The first term represents a deletion, the second an insertion, and the third a match or substitution. Each term refers to a smaller prefix pair, allowing dynamic programming.

Activity 3: Implement and test

The following pseudocode returns the distance; arrays use zero-based string indices.

function distance(a, b):
    m = length(a); n = length(b)
    create array D of size (m+1) x (n+1)
    for i = 0 .. m: D[i][0] = i
    for j = 0 .. n: D[0][j] = j
    for i = 1 .. m:
        for j = 1 .. n:
            cost = 0 if a[i-1] == b[j-1] else 1
            D[i][j] = min(D[i-1][j] + 1,
                          D[i][j-1] + 1,
                          D[i-1][j-1] + cost)
    return D[m][n]

Test the following pairs before checking the answers:

Source	Target	Expected distance
""	"abc"	3
"book"	"back"	2
"kitten"	"sitting"	3
"same"	"same"	0

Activity 4: Improve the algorithm

The full table uses O(mn) time and O(mn) memory. Observe that each row only needs the previous row. Adapt the algorithm to use two rows, then explain why the distance still remains correct. Describe why recovering the sequence of edits becomes harder when the full table is discarded.

Advanced challenge: If the task asks whether the distance is at most k, what does the inequality $d (a, b) \geq | | a | - | b | |$ tell you before running dynamic programming?

Discussion: what is one symbol?

This activity assumes the strings have already been split into the symbols being compared. Real Unicode text can be represented as bytes, code points, or user-perceived characters (grapheme clusters). These do not always produce the same numerical edit distance. Choose the unit deliberately; see Unicode Standard Annex #29 for grapheme cluster segmentation. Also consider Unicode normalization when equivalent text has different encoded forms.

References and further learning

R. A. Wagner and M. J. Fischer, “The String-to-String Correction Problem,” Journal of the ACM, 21(1), 168–173 (1974), DOI.
Unicode Consortium, Unicode Standard Annex #29: Unicode Text Segmentation.
Unicode & Grapheme-Safe Levenshtein — supplementary learning material on how Unicode normalization and grapheme segmentation affect the meaning of edit distance.