Dynamic programming  and shortest path problem Several months back, I asked in math.SE the following question


  I wonder 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? 


The reason I asked is because I always pictured the type of problems that could be solved by dynamic programming method as source-sink shortest path problems. In other words, the type of problems seemed to always have the interpretation as source-sink shortest path problems, but I was not sure if it was correct.

The only answer I have got so far is


  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. 


When I further asked:


  why is the example not able to be formulated into a source-sink
  shortest path problem in a network?


The reply is:


  I don't really see an easy way of doing it as a source-sink SPP. For
  the DP solution, the answer is obtained by scanning the array for the
  largest number.


I am now still not sure how DP solves the longest substring of ones in a 0,1 string, and whether this problem can be interpreted as a source-sink shortest path problem. Also I feel the answerer may run out of idea from his reply. Since my question may also be relevant to algorithm theory, I hope there will be some reply from this site.

Thanks and regards!
One standard view of dynamic programming is the following. Start with a recursive algorithm and then memoize it. By memoization we mean that solutions for intermediate problem instances/sub-problems are stored and not recomputed. If one can argue that the number of sub problems generated in the recursive algorithm for an instance of size $n$ is polynomial in $n$ then memoization leads to a polynomial time algorithm. A recursive algorithm for a problem instance $I$ generates, naturally, an associated DAG $G(I)$ whose nodes are the sub-problem instances and the arcs are the dependencies generated by the recursive algorithm on $I$. It is possible to interpret several different computational problems as solving some kind of shortest path problem on this DAG $G(I)$ (not all though). In these cases it is possible to take out the scaffolding of the recursive algorithm and memoization and directly use a shortest path algorithm in an associated graph. This should not lead one to conclude that all of dynamic programming can be reduced to shortest path computation.