Relationship Between Dynamic Programming (DP) and Directed Acyclic Graphs (DAG)

1. Subproblems and DAG Nodes:

• Dynamic Programming involves breaking down a problem into similar subproblems and these subproblems are solved independently and their result is used to solve the original problem.
• Nodes of Directed Acyclic Graph represents the subproblems. We can also say these nodes represent a state.

2. Transitions and DAG Edges:

• Like the Nodes represents subproblems in the DAG, similarly the edges represent transition.
• The transition from one subproblem to another is represented by an edge.

3. Cycles and Redundancy:

• The reason it’s a directed acyclic graph is that if there are cycles in the directed graph then some states would lead back to themselves after a series of transitions leading to redundancy.

Let’s take an example to understand the above points:

Problem: Finding Longest Path in Directed Acyclic Graphs (DAG):

The dp state and the transition in this case will be:

Let dp[v] denote the length of the longest path ending at the node v. Initialize all the positions in dp array as 1. Clearly,

For every edge from node u to node v, dp[v] = max (dp[u]+1)

At the end check for the maximum value in dp[] array, which will be the longest path in the DAG.

Pre-Requisite:
What is Directed Graph? | Directed Graph meaning
Dynamic Programming (DP) Tutorial with Problems

Every Dynamic Programming problem can be represented as a Directed Acyclic Graph(DAG). The nodes of the DAG represent the subproblems and the edges represents the transitions between the subproblems.