Several months back, I asked in math.SE the following questionI 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 isThe 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!
Dynamic programming  and shortest path problem
ds.algorithms;graph algorithms;dynamic programming