<p>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.</p>

CC BY-SA 3.0
2011-09-06T19:26:43.497Z
2011-09-06T19:26:43.497Z
Chandra Chekuri
<p>Shortest paths in DAGs are typically problems in NL and many times complete as well. A slightly "larger" class is LOGCFL (of course, we don't know if NL=?LOGCFL) where typical problems solvable with dynamic programming live. (Typical here means polynomial time. Unlike for example, DPs for knapsack type problems that take exponential time.)</p>

<p>As an example, consider the word problem on groupoids. You have a groupoid table and a word $a_1 ... a_n$ and the question is whether we can bracket the word in some way so that it evaluates to identity. (Note that the groupoid table need not be associative.) This problem is complete for LOGCFL. <a href="http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=113968">Here</a> is a reference; if I remember correctly, this goes back to Valiant.</p>

<p>So it would seem that typical DPs are more powerful than typical shortest path problems under typical complexity theoretic assumptions! Given the vagueness of what constitutes DP, this is as far as we can say.</p>

<p><strong>update</strong>: Suresh, here is one way to see. LOGCFL is a nondeterministic machine (like NP) but running in log space, polynomial time, with a stack. Think of the final solution as a witness. It will be a polynomial sized proof tree (because I assumed polynomial running time) with the children being the "smaller" subproblems etc.  But to traverse this tree, you will have to explore all children at a node and therefore you need a stack. (Because of the logspace restriction, you don't have space to record the witness and then check). </p>

CC BY-SA 3.0
2011-09-07T04:45:34.997Z
That's very interesting. I was not aware that LOGCFL was the natural class for many DPs. Is there any easy way to see this ?
Suresh Venkat
CC BY-SA 3.0
2011-09-07T12:45:11.727Z
What's a groupoid? The definition I know is that it's a category in which all morphisms have inverses, but somehow I don't think that's what you have in mind....
Neel Krishnaswami
CC BY-SA 3.0
2011-09-07T19:23:40.317Z
@Neel: When you decategorify the category-theoretic definition, you get the [algebraic definition](http://en.wikipedia.org/wiki/Groupoid#Algebraic) of groupoid. I assume what is being discussed here is a finite algebraic groupoid presented by a multiplication table.
Peter Shor 
CC BY-SA 3.0
2011-11-08T10:32:33.603Z
I think all so-called "incremental" DP algorithms (including that for the max contiguous 1-subsequence problem and many others) CAN be implemented as instances of "lightest" or "heaviest" s-t path problems. In an incremental" algorithm, the sums are restricted to the form: value of a subproblem plus the cost of a data item queried at that wire. I have a draft [paper](http://www.thi.informatik.uni-frankfurt.de/~jukna/) on this (things are in embryos stage, however).
Stasys
CC BY-SA 3.0
2011-09-07T04:15:34.437Z
2011-09-07T05:41:28.463Z
2011-09-07T05:41:28.463Z
V Vinay
<p>Here's a less formal answer that I hope nonetheless addresses the spirit of the question.</p>
<p>Many standard dynamic-programming algorithms are easily seen to be equivalent to shortest-path (or longest-path) in the DAG of subproblems (per Chandra's answer).  But some common ones that don't fit this pattern include <a href="https://en.wikipedia.org/wiki/Minimum-weight_triangulation#Variations" rel="nofollow noreferrer">minimum-weight triangulation of a polygon</a>, and <a href="https://en.wikipedia.org/wiki/Optimal_binary_search_tree#Knuth%27s_dynamic_programming_algorithm" rel="nofollow noreferrer">finding optimal binary search trees</a>.</p>
<p>To explain, consider the standard dynamic program for minimum-weight polygon triangulation.  Fix an input instance <span class="math-container">$p[1..n]$</span>, where <span class="math-container">$p[i]$</span> is the <span class="math-container">$i$</span>th point (in <span class="math-container">$\mathbb R^2$</span>).  For each pair <span class="math-container">$(i, j)$</span> with <span class="math-container">$1\le i &lt; j \le n$</span> and <span class="math-container">$j-i\ge 1$</span>, define <span class="math-container">$T(i, j)$</span> to be the optimal cost for the subproblem <span class="math-container">$p[i..j]$</span> formed by the <span class="math-container">$j-i+2$</span> points <span class="math-container">$p[i], p[i+1], \ldots, p[j]$</span>.  The final answer is <span class="math-container">$T(1, n)$</span>.  The recurrence relation is</p>
<p><span class="math-container">$$\mathbf{T(i, j)} = \begin{cases}
d(p[i], p[j]) &amp; (j=i+1) \\
\min \big\{ \mathbf{T(i, k) + T(k, j)} + d(p[i],p[j]) : k \in \{i+1,\ldots, j-1\}\big\}
&amp; (j &gt; i+1).
\end{cases}$$</span></p>
<p>If we consider the underlying DAG, the recurrence is not easily modeled as a shortest- or longest-path problem on that DAG, because, although the cost associated with the node for the subproblem <span class="math-container">$T(i, j)$</span> is expressed as a minimum of terms (as it would be in a shortest-path problem), each term involves the <em>sum</em> of two subproblems, <span class="math-container">$T(i, k) + T(k, j)$</span>.  As far as I know, because of this there is no natural re-interpretation as a shortest-path problem.</p>
<p>I think the combinatorial problem that more naturally underlies this dynamic program is finding a minimum-cost <em>binary search tree</em> in the underlying DAG, as is made explicit in the dynamic program for computing optimal binary search trees, which resembles this one very closely.</p>

CC BY-SA 4.0
2022-04-02T02:32:51.907Z
2022-04-02T20:13:48.090Z
2022-04-02T20:13:48.090Z
Neal Young
<p>Several months back, I asked in math.SE <a href="https://math.stackexchange.com/questions/36747/dynamic-programming-problem-and-shortest-path-problem">the following question</a></p>
<blockquote>
<p>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?</p>
</blockquote>
<p>The reason I asked is because I always pictured <a href="http://en.wikipedia.org/wiki/Bellman_equation#A_dynamic_decision_problem" rel="nofollow noreferrer">the type of problems</a> that could be solved by <a href="http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_mathematical_optimization" rel="nofollow noreferrer">dynamic programming method</a> 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.</p>
<p>The only answer I have got so far is</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>When I further asked:</p>
<blockquote>
<p>why is the example not able to be formulated into a source-sink shortest path problem in a network?</p>
</blockquote>
<p>The reply is:</p>
<blockquote>
<p>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.</p>
</blockquote>
<p>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.</p>
<p>Thanks and regards!</p>

CC BY-SA 3.0
2011-09-06T15:13:54.597Z
no such thing as a dynamic programming problem, DP is an algorithm framework. i guess you mean that DP can be interpreted as an algorithm for finding the shortest path in an appropriately defined graph. i suppose this is some graph of partial solutions. since you think that this can *always* be done, can you give one example?
Sasho Nikolov
CC BY-SA 3.0
2011-09-06T15:45:54.547Z
Please read Kaveh’s comment in [your question on meta](http://meta.cstheory.stackexchange.com/questions/1323/can-i-post-this-question-about-dynmaic-programming).
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-06T15:52:12.420Z
I knew it because you did not address the point which Kaveh raised.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-06T15:52:24.610Z
@Sasho: I am talking about whether the problems that can be solved by DP can be represented as source-sink shortest path problems.
Tim
CC BY-SA 3.0
2011-09-06T15:53:43.157Z
@Tsuyoshi: The two links to Wikipedia are the definitions I am using. What is your criterion?
Tim
CC BY-SA 3.0
2011-09-06T16:29:07.223Z
@Tim: The Wikipedia page you linked to is not in good shape.  As [pointed out on the talk page](http://en.wikipedia.org/wiki/Talk:Dynamic_programming#But_what_is_Dynamic_Programming.3F), the article does not define dynamic programming.  If a mod says on meta that your question is on topic if you define dynamic programming, and you don't, it doesn't make sense for you to hassle Tsuyoshi when he points it out.  If you don't know what a formal definition of dynamic programming is, you could ask that as a separate question.
Aaron Sterling
CC BY-SA 3.0
2011-09-06T16:35:28.623Z
A possibly on-topic question would be, "Does every problem that admits optimal substructure have graph-theoretic characterization X?"
Aaron Sterling
CC BY-SA 3.0
2011-09-06T16:37:05.130Z
@Aaron: (1) Although I appreciate your comment, I don't think your usage of "hassle" is appropriate. (2) I know what DP is, and it is basically given by the linked Wikipeida article. I don't know what "formal definition" is in your community.
Tim
CC BY-SA 3.0
2011-09-06T17:04:23.073Z
Sasho asked for an example. You ignored this. Tsuyoshi pointed out you didn't define the problem. You said you did even though the page you linked to clearly doesn't (which was why your response seemed rude to me). I've already suggested two questions you could ask. You have ignored this too.  Could you please write down what "dynamic programming problem" means and give a concrete example? Or don't.
Aaron Sterling
CC BY-SA 3.0
2011-09-06T17:19:51.410Z
@Aaron: Your comment is becoming irritating. (1) Sasho asked for an example for what I think can always be done. But I don't understand how giving an example can show a statement to be always true? I only know giving a counterexample can disprove something but not prove it. (2) the linked articles are definitions in my opinion, and I don't have a different/better one to contribute here. If you think they are not, you should ask yourself but not me to give a different one.
Tim
CC BY-SA 3.0
2011-09-06T17:21:07.400Z
(3) As I said before, your previous suggestions were appreciated. I haven't acted as what you strongly suggested, because I haven't think them through/necessary. You can think it as ignoring your order/command, and I will not try to make you not think this way.
Tim
CC BY-SA 3.0
2011-09-06T17:35:41.973Z
@Tim, the wikipedia article does not define dynamic programming mathematically, it is an intuitive concept but to prove results you need to give a *mathematical definition* for what is a DP algorithm, see for example "[Toward a Model for Backtracking and Dynamic Programming](http://www.cs.toronto.edu/~bor/pBT.pdf)" by Alekhnovich, Borodin, Buresh-Oppenheim, Impagliazzo, Magen, and Pitassi from CCC 2005. (also note that they call it *a* model for DP, not *the* model for DP, "what is the right model for DP?" is an active research area).
Kaveh
CC BY-SA 3.0
2011-09-06T17:45:03.203Z
You can alternatively define another DP model (a polynomial size sequence and a simple low complexity function that computes the value of the $n$-th member from previous ones. I don't know if SPP is complete for P or not, but if it is and your definition of DP is a subset of P then the answer is yes. And if it is not complete for P (but say is hard for $L$) and your function filling the entries of the sequence is not very very low complexity (not even $TC^0$) then we cannot show that we cannot reduce DP algorithms to SPP because that would separate that complexity class from the class for SPP.
Kaveh
CC BY-SA 3.0
2011-09-06T18:46:41.270Z
Kaveh pointed out on meta that we cannot talk about a property common to all the DP-based algorithms without first rigorously defining what “DP-based algorithms” are, and that defining DP rigorously is not at all trivial.  If you had never considered about defining DP rigorously (I had not), his comment should have been surprising to you and motivated you to learn about them if you care about your question.  Instead, you basically dismissed his comment and posted your question without even acknowledging his help.  (more)
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-06T18:46:47.263Z
(cont’d)  Then, you edited the title of your question after Sasho pointed out that “dynamic programming problem” does not make sense, and you talked back to him without even thanking him.  And then your impolite replies to Aaron’s comments.  I cannot help you simply because of lack of my knowledge, but I am afraid that your thankless attitude may not do any good to anyone including you.
Tsuyoshi Ito
CC BY-SA 3.0
2011-09-06T19:22:08.683Z
@Tsuyoshi: I am speechless on your comments. You put a lot of nonexistent things on my motivations: "dismiss ...","without even acknowledging his help", "edited ... and you talked back to him without even thanking him", "impolite replies". To be clear, I won't type "thanks" to every comment, but it doesn't mean I am not grateful to any form of help. Moreover, I am not into condescending, order-making and label-putting comments. This is just who I am, you can think of me as a thankless person, I will not try to convince you otherwise and I won't care whether you are here sincere to help.
Tim
CC BY-SA 3.0
2011-09-06T19:42:06.783Z
I think we should err on others acting nicely than erring in the other direction, written medium is not as expressive as face to face discussions. :) I guess that Tim didn't notice that Wikipedia article is not giving a mathematical definition of DP that can be used for answering his question. It would be nice if at some point someone adds a section to the Wikipedia article about proposed mathematical models for DP algorithms.
Kaveh
CC BY-SA 3.0
2011-09-06T20:12:27.727Z
I believe Tim misunderstood my question. You claim that *every* DP algorithm (for some notion of a DP algorithm) can be interpreted as a shortest path computation. For the sake of intuition and motivation (not as a proof!) I want you to give me *one* DP algorithm and an explanation how it corresponds to a shortest path computation. In the meantime though @Chandra Chekuri beat you to it, sort of.
Sasho Nikolov
CC BY-SA 3.0
2011-09-06T22:04:23.723Z
I think everyone needs to take a break here :). @Tim, I think Chandra has probably the clearest answer you're going to get, mainly because the notion of "what is dynamic programming" is not completely well defined.
Suresh Venkat
<ds.algorithms><graph-algorithms><shortest-path><dynamic-programming>
Dynamic programming and shortest path problem
Tim
# Dynamic programming and shortest path problem

(Asked by: username_0 on 2011-09-06)

Several months back, I asked in math.SE [the following question](https://math.stackexchange.com/questions/36747/dynamic-programming-problem-and-shortest-path-problem)

> 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](http://en.wikipedia.org/wiki/Bellman_equation#A_dynamic_decision_problem) that could be solved by [dynamic programming method](http://en.wikipedia.org/wiki/Dynamic_programming#Dynamic_programming_in_mathematical_optimization) 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!

**Tags:** ds.algorithms, graph-algorithms, shortest-path, dynamic-programming
> **Comments:**
> **username_1**: no such thing as a dynamic programming problem, DP is an algorithm framework. i guess you mean that DP can be interpreted as an algorithm for finding the shortest path in an appropriately defined graph. i suppose this is some graph of partial solutions. since you think that this can *always* be done, can you give one example?  
> **username_2**: Please read Kaveh’s comment in [your question on meta](http://meta.cstheory.stackexchange.com/questions/1323/can-i-post-this-question-about-dynmaic-programming).  
> **username_2**: I knew it because you did not address the point which Kaveh raised.  
> **username_0**: @Sasho: I am talking about whether the problems that can be solved by DP can be represented as source-sink shortest path problems.  
> **username_0**: @Tsuyoshi: The two links to Wikipedia are the definitions I am using. What is your criterion?  
> **username_3**: @Tim: The Wikipedia page you linked to is not in good shape.  As [pointed out on the talk page](http://en.wikipedia.org/wiki/Talk:Dynamic_programming#But_what_is_Dynamic_Programming.3F), the article does not define dynamic programming.  If a mod says on meta that your question is on topic if you define dynamic programming, and you don't, it doesn't make sense for you to hassle Tsuyoshi when he points it out.  If you don't know what a formal definition of dynamic programming is, you could ask that as a separate question.  
> **username_3**: A possibly on-topic question would be, "Does every problem that admits optimal substructure have graph-theoretic characterization X?"  
> **username_0**: @Aaron: (1) Although I appreciate your comment, I don't think your usage of "hassle" is appropriate. (2) I know what DP is, and it is basically given by the linked Wikipeida article. I don't know what "formal definition" is in your community.  
> **username_3**: Sasho asked for an example. You ignored this. Tsuyoshi pointed out you didn't define the problem. You said you did even though the page you linked to clearly doesn't (which was why your response seemed rude to me). I've already suggested two questions you could ask. You have ignored this too.  Could you please write down what "dynamic programming problem" means and give a concrete example? Or don't.  
> **username_0**: @Aaron: Your comment is becoming irritating. (1) Sasho asked for an example for what I think can always be done. But I don't understand how giving an example can show a statement to be always true? I only know giving a counterexample can disprove something but not prove it. (2) the linked articles are definitions in my opinion, and I don't have a different/better one to contribute here. If you think they are not, you should ask yourself but not me to give a different one.  
> **username_0**: (3) As I said before, your previous suggestions were appreciated. I haven't acted as what you strongly suggested, because I haven't think them through/necessary. You can think it as ignoring your order/command, and I will not try to make you not think this way.  
> **username_4**: @Tim, the wikipedia article does not define dynamic programming mathematically, it is an intuitive concept but to prove results you need to give a *mathematical definition* for what is a DP algorithm, see for example "[Toward a Model for Backtracking and Dynamic Programming](http://www.cs.toronto.edu/~bor/pBT.pdf)" by Alekhnovich, Borodin, Buresh-Oppenheim, Impagliazzo, Magen, and Pitassi from CCC 2005. (also note that they call it *a* model for DP, not *the* model for DP, "what is the right model for DP?" is an active research area).  
> **username_4**: You can alternatively define another DP model (a polynomial size sequence and a simple low complexity function that computes the value of the $n$-th member from previous ones. I don't know if SPP is complete for P or not, but if it is and your definition of DP is a subset of P then the answer is yes. And if it is not complete for P (but say is hard for $L$) and your function filling the entries of the sequence is not very very low complexity (not even $TC^0$) then we cannot show that we cannot reduce DP algorithms to SPP because that would separate that complexity class from the class for SPP.  
> **username_2**: Kaveh pointed out on meta that we cannot talk about a property common to all the DP-based algorithms without first rigorously defining what “DP-based algorithms” are, and that defining DP rigorously is not at all trivial.  If you had never considered about defining DP rigorously (I had not), his comment should have been surprising to you and motivated you to learn about them if you care about your question.  Instead, you basically dismissed his comment and posted your question without even acknowledging his help.  (more)  
> **username_2**: (cont’d)  Then, you edited the title of your question after Sasho pointed out that “dynamic programming problem” does not make sense, and you talked back to him without even thanking him.  And then your impolite replies to Aaron’s comments.  I cannot help you simply because of lack of my knowledge, but I am afraid that your thankless attitude may not do any good to anyone including you.  
> **username_0**: @Tsuyoshi: I am speechless on your comments. You put a lot of nonexistent things on my motivations: "dismiss ...","without even acknowledging his help", "edited ... and you talked back to him without even thanking him", "impolite replies". To be clear, I won't type "thanks" to every comment, but it doesn't mean I am not grateful to any form of help. Moreover, I am not into condescending, order-making and label-putting comments. This is just who I am, you can think of me as a thankless person, I will not try to convince you otherwise and I won't care whether you are here sincere to help.  
> **username_4**: I think we should err on others acting nicely than erring in the other direction, written medium is not as expressive as face to face discussions. :) I guess that Tim didn't notice that Wikipedia article is not giving a mathematical definition of DP that can be used for answering his question. It would be nice if at some point someone adds a section to the Wikipedia article about proposed mathematical models for DP algorithms.  
> **username_1**: I believe Tim misunderstood my question. You claim that *every* DP algorithm (for some notion of a DP algorithm) can be interpreted as a shortest path computation. For the sake of intuition and motivation (not as a proof!) I want you to give me *one* DP algorithm and an explanation how it corresponds to a shortest path computation. In the meantime though @Chandra Chekuri beat you to it, sort of.  
> **username_5**: I think everyone needs to take a break here :). @Tim, I think Chandra has probably the clearest answer you're going to get, mainly because the notion of "what is dynamic programming" is not completely well defined.  

---

## 3 answers

### Answer by username_6 on 2011-09-06. Score: 14

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.


---

### Answer by username_7 on 2011-09-07. Score: 10

Shortest paths in DAGs are typically problems in NL and many times complete as well. A slightly "larger" class is LOGCFL (of course, we don't know if NL=?LOGCFL) where typical problems solvable with dynamic programming live. (Typical here means polynomial time. Unlike for example, DPs for knapsack type problems that take exponential time.)

As an example, consider the word problem on groupoids. You have a groupoid table and a word $a\_1 ... a\_n$ and the question is whether we can bracket the word in some way so that it evaluates to identity. (Note that the groupoid table need not be associative.) This problem is complete for LOGCFL. [Here](http://ieeexplore.ieee.org/xpl/freeabs_all.jsp?arnumber=113968) is a reference; if I remember correctly, this goes back to Valiant.

So it would seem that typical DPs are more powerful than typical shortest path problems under typical complexity theoretic assumptions! Given the vagueness of what constitutes DP, this is as far as we can say.

**update**: Suresh, here is one way to see. LOGCFL is a nondeterministic machine (like NP) but running in log space, polynomial time, with a stack. Think of the final solution as a witness. It will be a polynomial sized proof tree (because I assumed polynomial running time) with the children being the "smaller" subproblems etc. But to traverse this tree, you will have to explore all children at a node and therefore you need a stack. (Because of the logspace restriction, you don't have space to record the witness and then check).

> **Comments:**
> **username_5**: That's very interesting. I was not aware that LOGCFL was the natural class for many DPs. Is there any easy way to see this ?  
> **username_8**: What's a groupoid? The definition I know is that it's a category in which all morphisms have inverses, but somehow I don't think that's what you have in mind....  
> **username_9**: @Neel: When you decategorify the category-theoretic definition, you get the [algebraic definition](http://en.wikipedia.org/wiki/Groupoid#Algebraic) of groupoid. I assume what is being discussed here is a finite algebraic groupoid presented by a multiplication table.  
> **username_10**: I think all so-called "incremental" DP algorithms (including that for the max contiguous 1-subsequence problem and many others) CAN be implemented as instances of "lightest" or "heaviest" s-t path problems. In an incremental" algorithm, the sums are restricted to the form: value of a subproblem plus the cost of a data item queried at that wire. I have a draft [paper](http://www.thi.informatik.uni-frankfurt.de/~jukna/) on this (things are in embryos stage, however).  

---

### Answer by username_11 on 2022-04-02. Score: 2

Here's a less formal answer that I hope nonetheless addresses the spirit of the question.

Many standard dynamic-programming algorithms are easily seen to be equivalent to shortest-path (or longest-path) in the DAG of subproblems (per Chandra's answer). But some common ones that don't fit this pattern include [minimum-weight triangulation of a polygon](https://en.wikipedia.org/wiki/Minimum-weight_triangulation#Variations), and [finding optimal binary search trees](https://en.wikipedia.org/wiki/Optimal_binary_search_tree#Knuth%27s_dynamic_programming_algorithm).

To explain, consider the standard dynamic program for minimum-weight polygon triangulation. Fix an input instance $p[1..n]$, where $p[i]$ is the $i$th point (in $\mathbb R^2$). For each pair $(i, j)$ with $1\le i < j \le n$ and $j-i\ge 1$, define $T(i, j)$ to be the optimal cost for the subproblem $p[i..j]$ formed by the $j-i+2$ points $p[i], p[i+1], \ldots, p[j]$. The final answer is $T(1, n)$. The recurrence relation is

$$\mathbf{T(i, j)} = \begin{cases}
d(p[i], p[j]) & (j=i+1) \\
\min \big\{ \mathbf{T(i, k) + T(k, j)} + d(p[i],p[j]) : k \in \{i+1,\ldots, j-1\}\big\}
& (j > i+1).
\end{cases}$$

If we consider the underlying DAG, the recurrence is not easily modeled as a shortest- or longest-path problem on that DAG, because, although the cost associated with the node for the subproblem $T(i, j)$ is expressed as a minimum of terms (as it would be in a shortest-path problem), each term involves the *sum* of two subproblems, $T(i, k) + T(k, j)$. As far as I know, because of this there is no natural re-interpretation as a shortest-path problem.

I think the combinatorial problem that more naturally underlies this dynamic program is finding a minimum-cost *binary search tree* in the underlying DAG, as is made explicit in the dynamic program for computing optimal binary search trees, which resembles this one very closely.


---

