A very common technique in algorithm design is divide and conquer. Hereby, the problem to solve is split into several sub-problems that are solved individually. After they have been solved, their solutions are combined to a solution into the original problem. A prominent example for a divide-and-conquer algorithm is merge sort. Merge sort splits the array in half, applies itself recursively to each of the halves and recombines the two sorted halves into a fully sorted array using a linear-time algorithm.
In some problems we want to solve, there is however the situation that some of the sub-problems appear several times, i.e. we have overlapping sub-problems. A straightforward recursive implementation would recompute their solution over and over again. To avoid unnecessary recomputation, we can use memory to memoize the result of the first solution of such a subproblem and reuse the memoized value in any further situation that solution of the sub-problem is required.
Dynamic programming is a programming technique to solve certain mathematical optimization problems using memoization. An optimization problem is a problem where there are multiple valid solutions of which each has a certain cost. One is then interested in finding the best solution with respect to that cost. For example, in route planning there may be several routes that get you from \(s\) to \(t\text{.}\) However each route has a certain length and so there will be shorter and longer routes. Hence, routing is an optimization problem because one is interested in finding the shortest route.
Dynamic programming is applicable if the optimization problem has so-called optimal substructure. This means that problem can be, in a way similar to divide-and-conquer, partitioned into sub-problems and the optimal solution of the original problem can be efficiently obtained from the optimal solutions of the sub-problems. Finding the shortest route/path from a node \(s\) in a directed graph to another node \(t\) is an optimization problem that possesses optimal substructure: Having found the shortest path from \(s\) to each predecessor of \(t\) allows us to quickly identify the shortest path to \(t\) itself by locally considering all incoming edges of \(t\) (see Figure 5.4.1).
Figure5.4.1.We can compute the length of the shortest path from \(s\) to \(t\) from the lengths of the shortest paths to \(t\)'s predecessors.
We will first discuss two examples that have overlapping sub-problems to investigate how we can replace straightforward recursion using memoization. Then, we will consider some optimization problems that have optimal substructure and devise dynamic programming algorithms to solve them.
Subsection5.4.1Computing Fibonacci Numbers
We start with a simple example that has overlapping sub-problems: Computing Fibonacci numbers. These are recursively defined as follows:
\begin{equation*}
F_0\defeq 0\qquad F_1\defeq 1\qquad F_n\defeq F_{n-1}+F_{n-2}\text{ for }n>1
\end{equation*}
A first straightforward recursive implementation looks as follows:
Let's consider the call fib(6). Figure 5.4.2 shows the call tree of fib(6).
Figure5.4.2.The call tree of fib(6). Each node corresponds to an argument to a call to fib. An edge indicates that the call with the upper argument calls fib with the lower argument.
The number of calls fib(n) creates is \(F_n\text{.}\) For example, \(F_{45}=1,836,311,903\text{.}\) So, assuming that one call takes 10 nanoseconds, fib(45) will take 45 seconds to compute. This can be drastically accelerated because the simple recursive scheme computes the same calls multiple times. For example, fib(4) is computed twice. By memorizing the result of the first call, all subsequent calls with the same argument can be avoided.
This version uses a table to memoize all results of recursive calls and checks if the result of a call has already been computed in the past. If so, that value is read from the table and not recomputed. However, when looking at the computation of the Fibonacci numbers more closely, one observes that we only need the last two values, so memoizing everything is not necessary. We can achieve the same with an iterative program that uses only two local variables:
unsigned fib_iterative(unsigned n) {
unsigned f1 = 1;
unsigned f2 = 0;
unsigned f = n;
while (n-- > 1) {
f = f1 + f2;
f2 = f1;
f1 = f;
}
return f;
}
multiplications. This can be optimized a little by the following observation: The terms \(k!\) and \((n-k)!\) are intermediate results when computing \(n!\text{.}\) Hence, we can memorize their value and re-use it in the computation of \(n!\) like so:
\begin{equation*}
\binom nk = \frac{n(n-1)\cdots (n-m+1)}{m!}\qquad\text{with } m \defeq \min(k, n-k)\le n/2
\end{equation*}
Then, we only need \((n-(n-m+1))+(m-2) + 1=2m-2\) multiplications. This means \(n-2\) multiplications in the worst case because \(m\lt n/2\text{.}\)
However, the nominator and denominator can get quite large when computing the binomial coefficient this way. If we assume that we compute with unsigned ints of 32-bit length, the largest \(n\) with \(n!\lt 2^{32}\) is \(n=12\text{.}\) We can empirically determine that the largest binomial coefficient that we can compute with the above equation without overflow is \(\binom{17}{8}=24310\text{.}\) However, the largest binomial coefficient we can represent with 32-bit is way larger.
One way of making the computation of larger binomial coefficients feasible and efficient is to use the following recurrence equation
\begin{equation}
\binom nk = \binom{n-1}{k-1}+\binom{n-1}{k}\qquad\qquad \binom n0=\binom nn=1\tag{5.2}
\end{equation}
that directly leads to what is known as Pascal's triangle:
These recursive equations directly yield a recursive program:
unsigned int binomial(unsigned int n, unsigned int k) {
if (k > n)
return 0;
if (k == 0 || k == n)
return 1;
return binomial(n - 1, k - 1) + binomial(n - 1, k);
}
and the first summand is also used to to compute \(\binom nk\text{.}\) Without memoization, this program performs exponentially many calls in \(n\text{.}\) Memoizing the partial results then yields a more efficient algorithm that we develop in the following.
which is equivalent to saying that Pascal's triangle is symmetrical. This means that we never need to memoize a binomial coefficient larger than \(\lfloor n/2\rfloor\text{.}\) From (5.2) follows that we don't need to compute binomial coefficients larger than \(k\) in order to compute \(\binom nk\text{.}\) So, to compute \(\binom nk\text{,}\) we need a two-dimensional table with \(k\) columns and \(n\) rows. For example, this is the table for computing \(\binom 73\text{:}\)
The following code implements the memoization technique to compute binomial coefficients:
unsigned int binomial_table(unsigned int N, unsigned int K) {
if (K > N)
return 0;
if (K > N - K)
K = N - K;
if (K == 0)
return 1;
unsigned table[N + 1][K + 1];
for (unsigned n = 0; n <= N; n++) {
table[n][0] = 1;
unsigned const end = n < K ? n : K;
for (unsigned k = 1; k <= end; k++)
table[n][k] = table[n - 1][k] + table[n - 1][k - 1];
for (unsigned i = end + 1; i <= K; i++)
table[n][i] = 0;
}
return table[N][K];
}
Note that we could even further optimize this code because in order to compute the k-th row of the table, we only need the previous row. So we actually don't need to memoize all rows but just two and “double-buffer” them.
Subsection5.4.3Computing the Minimum Edit Distance
Let us turn to our first real dynamic programming algorithm. Here, we are not only considering overlapping sub-problems but also optimal substructure.
Given two words \(a\) and \(b\text{,}\) the minimum edit distance (sometimes also called the Levenshtein distance) between \(a\) and \(b\) is the minimum number of edit operations (delete/replace/add a character) to transform \(a\) to \(b\text{.}\) Solving edit distance problems is relevant in fuzzy string search settings, such as spell checking. Also, problems like computing genome sequence alignments are related very closely to edit distance problems.
Trivially, we can transform tore into tag by four delete and three add operations: First delete all letters and then add the three letters t, a, g. This results in seven edit operations. So each sequence of edit operations that takes us from tore to tag has a certain cost, i.e. the number of additions, replacements, and deletions.
However, we are interested in the shortest/minimum sequence of edits which in this example has three edit operations: Keep t (no edit operations), replace o by a, replace r by g and delete e.
Let us discuss the edit distance problem more formally.
Definition5.4.3.Minimum Edit Distance.
The minimum edit distance of two words \(a\) and \(b\)up to positions \(i\) and \(j\) is defined as follows:
\begin{equation*}
\begin{array}{lcl}
\edist_{a,b}\amp:\amp\{0,\dots,|a|\}\times\{0,\dots,|b|\}\to\Nat \\
\edist_{a,b}(0, j) \amp \mapsto \amp j \\
\edist_{a,b}(i, 0) \amp \mapsto \amp i \\
\edist_{a,b}(i, j) \amp \mapsto \amp
\min
\begin{cases}
% TODO@hack: Hier müsste meiner Meinung nach vom Sinn her die Wörter anfügen und löschen getauscht werden
\edist_{a,b}(i-1,j) + 1 \amp \text{delete} \\
\edist_{a,b}(i,j-1) + 1 \amp \text{add} \\
\edist_{a,b}(i-1,j-1) \amp \text{if } a_i = b_j\qquad \text{ keep} \\
\edist_{a,b}(i-1,j-1)+1 \amp \text{if } a_i \ne b_j\qquad \text{ replace}
\end{cases}
\end{array}
\end{equation*}
From the recursive definition of \(\edist\) we can see that some partial results are used multiple times. Hence, we will also use to memoization to compute the edit distance of two words efficiently. Let us apply Definition 5.4.3 to the example above.
Let us first consider the top row and left column. The entries of the first row correspond to the costs to transform the empty word to the words \(\varepsilon\text{,}\)t, ta, tag by adding the respective characters.
Accordingly, the entries in the first column corresponds to the costs to get to the empty word from \(\varepsilon\text{,}\)t, to, tor, tore by deleting the respective letters.
The remaining table entries are filled with the minimum expression of Definition 5.4.3. For example, for the entry at (1, 1), the third case of the case distinction contributes the minimum value:
According to the definition in Definition 5.4.3, the entry in row \(i\) and column \(j\) equals to the minimum edit distance of the words \(a[1:i]\) and \(b[1:j]\text{.}\) The elements of the first row and column are always the same for each pair of words. All other elements can be computed from the elements above, left, and above left.
Computing the minimum edit distance is an optimization problem because we are looking not only for the cost of some sequence of edits but for the minimum cost. The property of this problem that makes it amenable to be solved with dynamic programming is that it possesses optimal substructure: The optimal solution \(\edist(i,j)\) can be computed from the optimal solutions \(\edist(i,j-1)\text{,}\)\(\edist(i-1,j)\text{,}\)\(\edist(i-1,j-1)\) of the respective sub-problems.
