"Dijkstra's algorithm for shortest paths can be seen as DP"
Really? Sure, if the graph is a dag, but then Dijkstra is overkill.
Hmm. I'll have to think about this one.
+1 for the Okasaki shoutout.
Really? Sure, if the graph is a dag, but then Dijkstra is overkill.
Hmm. I'll have to think about this one.
+1 for the Okasaki shoutout.
But my main point was: if one can look at the shortest-path problem and formulate something like
distance(v) = min_{u->v} (distance(u) + edge_length(u, v))
then one probably has a handle on whatever it is that's hard about dynamic programming. Actually Wikipedia cites some references that consider Dijkstra's algorithm a case of DP: https://en.wikipedia.org/w/index.php?title=Dijkstra%27s_algo... and the same text (Wikipedia doesn't care about “self-plagiarism”) is also on the DP page where Dijkstra's algorithm is given as the first example: https://en.wikipedia.org/w/index.php?title=Dynamic_programmi...