Re:Google Interview Questions Deconstructed: The Knight’s Di...
by tyrust on Wednesday October 07, 2020 @04:33PM
(#24712400)
>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.
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-...