Dynamic programming can be applied to any problem
that observes the *principle 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
partial solution itself.
For example, to decide whether to extend an approximate string matching
by a substitution, insertion, or deletion, we do not need to know exactly
which sequence of operations was 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 will be made based on the *consequences*
of previous decisions,
not the actual decisions themselves.

Problems do not satisfy the principle of optimality if the actual operations matter, as opposed to just the cost of the operations. Consider a form of edit distance where we are not allowed to use combinations of operations in certain particular orders. Properly formulated, however, most combinatorial problems respect the principle of optimality.

The biggest limitation on using dynamic programming is the number of partial
solutions we must keep track of.
For all of the examples we have seen, the partial solutions
can be completely described by specifying the stopping *places*
in the input.
This is because the
combinatorial objects being worked on (strings, numerical sequences,
and polygons) all have an implicit order defined upon their elements.
This order cannot be scrambled without completely changing the problem.
Once the order is fixed, there are relatively few possible stopping places
or states, so we get efficient algorithms.
If the objects are not
firmly ordered, however,
we have an exponential number of possible partial solutions
and are doomed to need an infeasible amount of memory.

To illustrate this, consider the following dynamic programming algorithm for
the traveling salesman problem, discussed in greater detail in [RND77].
Recall that solving a TSP means finding the order that visits
each site exactly once, while minimizing the total distance traveled
or cost paid.
Let *C*(*i*,*j*) to be the edge cost to travel directly from *i* to *j*.
Define to be
the cost of the optimal tour from *i* to 1 that
goes through each of the cities exactly once,
in any order.
The cost of the optimal TSP tour is
thus defined to be
and can be computed recursively by identifying the first edge in this
sequence:

using the basis cases

This recurrence, although somewhat complicated to understand,
is in fact correct.
However, each partial solution is described by
a vertex subset .
Since there are subsets of *n* vertices, we
require time and space to evaluate this recurrence.
Whenever the input objects do not have an inherent left-right order,
we are typically doomed to having an exponential-sized state space.
Occasionally this is manageable -
indeed, is a big improvement
over enumerating all *O*(*n*!) possible TSP tours.
Still, dynamic programming is most effective on well-ordered objects.

Mon Jun 2 23:33:50 EDT 1997