# Dynamic Programming as DAGs - Solution Always Shortest Path?

I've been trying to get a deeper understanding of how dynamic programming works and came across how it can be represented as directed acyclic graphs (DAGs). It's easy to see why, nodes represent the subproblems and directed edges represent which problem the subproblems help solve. Similar to a recursion tree but with repeated nodes removed and edges having a direction. However, many of the explanations for DAGs representing dynamic programming problems state that finding the shortest path of a DAG representing the problem also solves the dynamic programming version. Which to me does not make much sense.

I can see why this would be for a problem like Edit Distance. The edges simply represent the cost which we want to minimize hence the shortest path. But how would this work for the Longest Increasing Subsequence? The latter would require us to find the longest path to find the longest subsequence. My understanding is that we simply use the optimal substructure of the problem to follow edges from the nodes representing the base cases until reaching the desired solution. Which may or may not result in the shortest path on a DAG.

Here is an example (MIT lecture by Erik Demaine at 3:50) of the claim that the solution to dynamic programming problems is also the shortest path on a DAG. However, he does not explain why in that lecture or the previous one. And the other examples I've seen also make such claims without providing any proof. So is the solution for a dynamic programming problem always represented by the shortest path on a DAG or can it be represented by other paths as well?

• Honestly, I don't see how one path can represent the problem when the recurrence relation is not a min or max, e.g. when it is a sum (simplest example: Fibonacci numbers). Mar 8 at 16:00

$$A[j] = \min \{A[i] + f(i,j) | i < j\}$$
then it can be expressed as a shortest-path problem on a DAG (with each edge $$(i,j)$$ having length $$f(i,j)$$). If the recurrence relation has other forms, then it cannot.
Demaine does not say that dynamic programming can always be expressed as shortest path on a DAG. He writes on the board "DP $$\approx$$ shortest paths in some DAG": note that the $$\approx$$ is warning you that they are not exactly equivalent, but it's still a helpful intuition. Verbally, Demaine says "dynamic programming in some sense always is computng shortest paths on a DAG" (emphasis added). Note the "in some sense", which is letting you know that this statement is not 100% true but it's a helpful way to think about things.