What kinds of problems can be solved using Dynamic Programming? One property these problems
have is that if the optimal solution involves solving a subproblem, then it uses the optimal solution
to that subproblem. For instance, say we want to find the shortest path from A to B in a graph,
and say this shortest path goes through C. Then it must be using the shortest path from C to B.
Or, in the knapsack example, if the optimal solution does not use item n, then it is the optimal
solution for the problem in which item n does not exist. The other key property is that there
should be only a polynomial number of different subproblems. These two properties together allow
us to build the optimal solution to the final problem from optimal solutions to subproblems.
In the top-down view of dynamic programming, the first property above corresponds to being
able to write down a recursive procedure for the problem we want to solve. The second property
corresponds to making sure that this recursive procedure makes only a polynomial number of
different recursive calls. In particular, one can often notice this second property by examining
the arguments to the recursive procedure: e.g., if there are only two integer arguments that range
between 1 and n, then there can be at most n
2 different recursive calls.
Sometimes you need to do a little work on the problem to get the optimal-subproblem-solution
property. For instance, suppose we are trying to find paths between locations in a city, and some
intersections have no-left-turn rules (this is particulatly bad in San Francisco). Then, just because
the fastest way from A to B goes through intersection C, it doesn’t necessarily use the fastest way
to C because you might need to be coming into C in the correct direction. In fact, the right way
to model that problem as a graph is not to have one node per intersection, but rather to have one
node per hintersection, directioni pair. That way you recover the property you need.