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.