# Can I post this question about dynmaic programming?

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!

-
I think it is OK, but you should first define what you mean by a DP algorithm. For proving a negative result that some problem cannot be solved by some type of algorithms you first need a formal definition of what type of algorithms are. There has been some work on defining DP in recent years but it is still an active area of research AFAIK. – Kaveh Sep 6 '11 at 14:37