Draw a graph with vertices labeled 0 through N, then add edges i->(i+1) and i->(i+2). The answer is the number of paths from 0 to N.
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).
Whoa, this is something new for me. For e.g. how would you transform calculating nth fibonacci number into a graph problem?