Dynamic Programming
Overview
Dynamic programming is the paradigm in which, given a problem, a directed graph of subproblems
is defined. These subprograms are then solved in topological order. The inputs for any subproblem
may include the outputs of preceding subproblems. The solution to the orginal problem is then
computed from the solutions to the subproblems.
The hardest part of doing dynamic programming is realizing that your problem should be worked
that way. I have seen very smart students fail to see this. The second hardest part is identifying
the subproblems. Thirdly, you must write a program to compute a solution to each subproblem,
given the solutions to prior subproblems.
The subproblems may fall into different classes, requiring different algorithms rather than a uni-
form algorithm for all. We can see that in some of the problems below.
Paragraph Breaking
Given a sequence of n words, way, you need to decide on line breaks to optimize the resulting
paragraph. Let wi be the ith word, and xi its length. ith word. Your are given a messure of
the “goodness” of any paragraph. Your job is to find the “best” possible paragraph given that
sequence of words. We frequently measure this goodness in reverse: we define the “penalty” for
each possible line length and try to find the paragraph with minimum penalty. The output of
your problem is an increasing sequence (i1 , . . . ik such that the k th line of the best paragraph ends
at the ith
k word.
The time complexity of any paragraph breaking algorithm is Ω(n), since the algorithm must look
at each word at least once.
Trivial greedy algorithm. Suppose there is a maximum length L of any line, and the penalty
of any line is L minus the length of that line, except for the last line, which has no penalty. The
trivial algorithm is to end each line at the last possible position. This algorithm takes Θ(n) time.
Does it create the best paragraph?
General penalty. The greedy algorithm, which you use when typing, generally results in a
ragged right margin. For more sophisticated situations, such as books and published articles, a
line can be compressed or stretched. The penalty function is designed to make the right-hand
margin look smoother. Let L be the ideal total length of the words on a line, and M the maximum
allowed. The penalty is zero if the length of the line is L, and is larger if that length deviates
from M in either direction, except for the last line. The penalty of the paragraph is then the
sum of the penalties of the lines. There are n subproblems. For each 1 ≤ i ≤ n, define P [i]
to be the paragraph consisting of the words wi . . . wn . The subprograms are worked in reverse
order, starting with P [n] and ending with P [1], the solution to the original problem. The time
complexity depends on the penalty function.
1
Editing Distance. Given two strings u and v, of lengths n and m, respectively, what is the
cost of the changes that need to be made to u to make it v? We call that the editing distance
from u to v. An edit consists of a sequence of small changes, each of which has a given cost, and
the goal is to minimize that cost. Levenshtein distance is only one example. Let u[1 . . . i] prefix
of u consisting of the first i symbols; similarly v[1 . . . j]. If the editing cost function is simple,
such as for Levenshtein distance, we define the subproblem S[i, j] for all 0 ≤ i ≤ n, 0 ≤ j ≤ m
to be the cost of changing u[1 . . . i] to v[1 . . . j]. If the cost function is reasonably simple, such as
in the calse of Levenshtein distance, we let S[0, 0] = 0, then compute S[i, j] from the values of
S[i − 1, j − 1], S[i − 1, j], and S[i, j − 1].
Shortest or Longest Path. Given a directed acyclic graph G, we have two closely related
problems.
1. Given a “source” vertex s of G and a “target” vertex t, find the shortest directed path
through G from s to t.
2. Find the longest directed path through G.
Either of these problems can be enhanced by assigning a weight to each arc, measuring the cost
of a path instead of simply its number of arcs.
For either problem, let S[i] be the minimum length of any path from the source to i for problem
(a), or the maximum length of any path which ends at j for problem (b). The time complexity is
O(m), Where m is the number of arcs of G, provided we visit the vertices in topological order.
Remark. The Levenshtein edit distance problem reduces to (a).
Remark. The longest increasing subsequence problem reduces to (b).
Longest Monotone Subsequence. Given a sequence of numbers σ = x1 , x2 , . . . xn , find a
longest strictly monotone increasing subsequence of σ. For example, σ = 3, 2, 1, 6, 5, 4, 9, 8, 7 The
greatest length of any monotone increasing sequence of σ is 3, and there are many subsequences
of that length, such as 1, 6, 8.
Reduction of the LMS problem to the maximum length path problem. Let G = (V, E)
be the directed graph where V = {1, 2, 3, . . . n} and E = {i, j) : i < j and x[i] < x[j]}
The longest increasing subsequence problem can be solved in O(n2 ) time, using a fairly simple
algorithm. But there is a more sophisticated algorithm that takes O(n log n) time.
Maximum Contiguous Subsequence. Let x1 , . . . xn be a sequence of numbers, both positive
and negative. The problem is to select
P a contiguous subsequence of maximum sum, that is, to
choose 1 ≤ k ≤ ℓ ≤ n to maximize ℓi=k . The dynamic program has two kinds of subproblems:
A[i] = the maximum sum of any contiguous subsequence of σ whose last term is xi . B[i] = the
maximum sum of any contiguous subsequence of σ[1 . . . i]
A[i] = x[i]+max(0,A[i-1]);
B[i] = max(A[i],B[i-1]);
2
The solution is B[n].
Coin Row Problems There are two different dynamic programs for the standard icoin-row
problem. Let x[1], x[2], . . . x[n] be the values of the coins, where x[i] > 0 for all i. Recall that
the problem is to select a set of coins of maximum value, subject to the condition that no two
consecurive coins can be selected.
1. Let T [i] be the maximum value of a subset of the first i coins, subject to the condition that
no two consecurive coins can be selected.
int findmax()
{
T[0] = 0;
T[1] = x[1];
for(int i = 2; i <= n; i++)
T[i] = max(T[i-1],T[i-2]_x[i]);
return T[n];
}
2. Alternatively, let T [i] be the maximum value of any set which contains the ith coin, subject
to the condition that no two consecurive coins can be selected.
int findmax()
{
T[0] = 0; // even though there is no zeroth coin
T[1] = x[1];
T[2] = x[2];
for(iint i = 3; i <= n; i++)
T[i] = T[i] + max(T[i-2],T[i-3])
return max(T[n-1],T[n]);
}
3. Bellman Ford algorithm. Given a weighted digraph G with a designate start vertex 0,
find, for each vertex i, the minimum weight directed path from 0 to i, assuming G has no
negative weight cycle. Let n, m, be the number of vertices and arcs, respectively, of G.
Define the arclength of any path to be the number of arcs of that path. A trivial path at 0
has arclength 0. The problem is to find a minimum weight path from 0 to i, for each vertex
i.
We define (n − 1)m subproblems, The vertices of S are the subproblems Si,ℓ for 0 ≤ i, ℓ < n,
which is to find a minimum weight path from 0 to i whose arclength does not exceed ℓ
The source vertex of S is (0, 0). There is an arc from Si,ℓ to Si′ ,ℓ+1 for any i, i′ and for any
ℓ.
4. Floyd Warshall algorithm. Given a weighted digraph G, find the least weight path from i
to j, for any two vertices i and j of G.
3
Let the vertices be 1, . . . n. Let S be the graph of subproblems S has n3 vertices, Sub-
problems Wi,j for all i, j, the weight of the arc from i to j (possibly ∞), and Si,j,k for all
1 ≤ i, j, k ≤ n. The solution to Si,j,k is the least weight path from i to k which contains no
internal vertices greater than j. The arcs of S to Si,j,k are from Wi,j , Wi,k , Wj,k , Si,j−1,k ,
Si,j−1,j and Sj,j−1,k .
At the end of the algorithm, there are n2 solutions, namely {Si,n,j } for all 1 ≤ i, k ≤ n.