The Algorithm Design Manual Second Edition

When are Dynamic Programming Algorithms Correct?

Dynamic programming algorithms are only as correct as the recurrence relations

they are based on. Suppose we define LP [i, j] as a function denoting the length of

the longest simple path from i to j. Note that the longest simple path from i to j

had to visit some vertex x right before reaching j. Thus, the last edge visited must

be of the form (x, j). This suggests the following recurrence relation to compute

the length of the longest path, where c(x, j) is the cost/weight of edge (x, j):

LP [i, j] = max

(

x,j)

∈E

LP [i, x] + c(x, j)

The idea seems reasonable, but can you see the problem? I see at least two of

them.

First, this recurrence does nothing to enforce simplicity. How do we know that

vertex j has not appeared previously on the longest simple path from i to x? If it

did, adding the edge (x, j) will create a cycle. To prevent such a thing, we must

define a different recursive function that explicitly remembers where we have been.

Perhaps we could define LP



[i, j, k] to be the function denoting the length of the

longest path from i to j avoiding vertex k? This would be a step in the right

direction, but still won’t lead to a viable recurrence.

A second problem concerns evaluation order. What can you evaluate first? Be-

cause there is no left-to-right or smaller-to-bigger ordering of the vertices on the

graph, it is not clear what the smaller subprograms are. Without such an ordering,

we get are stuck in an infinite loop as soon as we try to do anything.

Dynamic programming can be applied to any problem that observes the princi-

ple of optimality. Roughly stated, this means that partial solutions can be optimally

extended with regard to the state after the partial solution, instead of the specifics

of the partial solution itself. For example, in deciding whether to extend an approx-

imate string matching by a substitution, insertion, or deletion, we did not need to

---

8 . 7

L I M I T A T I O N S O F D Y N A M I C P R O G R A M M I N G : T S P

303

know which sequence of operations had been performed to date. In fact, there may

be several different edit sequences that achieve a cost of C on the first p characters

of pattern P and t characters of string T . Future decisions are made based on the

consequences of previous decisions, not the actual decisions themselves.

Problems do not satisfy the principle of optimality when the specifics of the

operations matter, as opposed to just the cost of the operations. Such would be

the case with a form of edit distance where we are not allowed to use combinations

of operations in certain particular orders. Properly formulated, however, many

combinatorial problems respect the principle of optimality.