Dynamic programming problem and shortest path problem

Question

I was wondering

1. if any dynamic programming problem can always be converted to a source-sink shortest path problem in a network with source and sink nodes given? And vice versa?
2. Is any dynamic programming problem essentially a linear integer programming problem?
3. if in a network, the shortest path length between every vertices defines a metric on the set of vertices of the network?

Thanks and regards!

Answer 1

For the first part of (1): The answer is no. The simplest example off the top of my head is the longest substring of ones in a 0,1 string. The typical DP solution would be to use a 1D array and store the length of the longest substring up that includes the $i$-th character in the $i$-th coordinate.

For the vice-versa part of (1): Yes.

The not-so-direct answer for (1) and (2) is that dynamic programming should be seen as a method and not a set of problems. It just describes a general paradigm for solving problems by memoizing solutions to subproblems and building on them. In that sense, it really is some kind of extension of greedy algorithms, only that it can build on multiple subproblems instead of just one in the case of greedy algorithms.

For part (3): This holds for finite undirected graphs with positive weights. It also holds for countably infinite graphs, but does not hold in general for graphs of larger cardinality.