>On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach. This concept was introduced to

>On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach. This concept was introduced to me back in my algorithms class and is pretty useful. For anyone looking for a longer explanation, page 167 of the textbook [0] has the nugget and some examples: >Every dynamic program has an underlying dag (directed acyclic graph) structure: think of each node as representing a subproblem, and each edge as a precedence constraint on the order in which the subproblems can be tackled. [0] - PDF: http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-...