[svat]

Hmm, I wrote that from vague memory, and perhaps that's debatable! (There seem to be different communities that use “dynamic programming” slightly differently.)

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