For anybody wondering, this is a disguised 'count number of walks of length k on a graph' problem.
On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach.
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-...
Whoa, this is something new for me. For e.g. how would you transform calculating nth fibonacci number into a graph problem?
This is still pretty specific to counting paths in the same way the original knight problem is, though.
The other comment is talking about how you represent each state for the recursive function as a vertex, then connect it to its dependencies (basically taking the recursion tree, but merging identical calls).
Consider the following graph. The nth fibonnaci number is the number of possible walks from n to 1.
(I made a mistake in the picture, there should be an edge from 2 to 1).