1
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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). $\endgroup$
    – Nathaniel
    Mar 8 at 16:00

1 Answer 1

2
$\begingroup$

Dynamic programming can often be expressed as a shortest path problem on a DAG, but not always. It depends on the recurrence relation. If the recurrence relation has the form

$$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.

To see how a dynamic programming algorithm for longest increasing subsequence can be viewed as a shortest path in a dag, see Chapter 6.2 of Algorithms by Dasgupta, Papadimitriou, and Vazirani, which explains this in detail. (They explain how it is a longest-path problem, but by negating all edge weights, we obtain a shortest-path problem.)

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.