4 ms·

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 p

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.

tyrust 6y ago
>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-...
avinassh 6y ago
> On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach. Whoa, this is something new for me. For e.g. how would you transform calculating nth fibonacci number into a graph problem?
- anandoza 6y ago
  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).
  - deleted 6y ago
    [deleted]
- boyobo 6y ago
  https://ibb.co/BGj5nDn https://ibb.co/BGj5nDn 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).

tyrust 6y ago

>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-...

avinassh 6y ago

> On a more general note, anytime a problem admits a dynamic programming solution, there almost always is a graph based approach. Whoa, this is something new for me. For e.g. how would you transform calculating nth fibonacci number into a graph problem?

anandoza 6y ago
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).
- deleted 6y ago
  [deleted]
boyobo 6y ago
https://ibb.co/BGj5nDn https://ibb.co/BGj5nDn 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).