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 DP 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 am not sure if I can post my question on this site?
Thanks and regards!
