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.
Table of Content
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.
DP on Directed Graphs
What happens when the graph is not Directed Acyclic Graphs (DAG)?
If the graph contains a cycle, then some states would lead back to themselves after a series of transitions. This would lead to infinite calculations. Thus, answer will not exist if the graph is cyclic in this case. As shown in below image, we potentially keep traversing the cycle indefinitely, making it impossible to find the longest path.
DP on Directed Graphs
How to Solve Dynamic Programming (DP) Problems on Directed Graphs:
Let us consider few problems which will tell how to define the states and make the transition:
Count the number of different ways to reach a node:
Given a Directed Acyclic Graph consisting of N nodes and M edges. The task is to determine the number of different ways to reach Node N from Node 1.
Solution: The problem can be solved in following steps:
1. Define the States: As mentioned above each Nodes of Directed Acyclic Graph represents a state. Let dp[v] be the number of ways to reach Node N from the vertex v.
2. Make the Transitions: Like the Nodes represents states in the DAG, similarly the edges represent transition. Thus dp[v] can be calculated by:
dp[v] = Σdp[u], for every edge v->u
3. Topological Consideration: We process the nodes topologically i.e., if edge v->u exists then dp[u] should be computed before dp[v].
Hence ,dp[1] will be our final answer.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>using namespace std;// Recursive function to perform depth-first search// and calculate the number of ways to reach Node N from// vertex currint dfs(int n, vector<vector<int> >& adj, vector<int>& dp, vector<int>& vis, int curr){ // If the node has already been visited, return its // stored value if (vis[curr] == 1) return dp[curr]; // Mark the current node as visited vis[curr] = 1; // Traverse all adjacent nodes and recursively calculate // the number of ways for (auto x : adj[curr]) { if (!vis[x]) { dfs(n, adj, dp, vis, x); } // Update the number of ways to reach Node N from // the current node dp[curr] += dp[x]; } // Return the calculated value for the current node return dp[curr];}// Function to calculate the number of ways to reach Node N// from Node 1int noOfWays(int n, vector<vector<int> >& edges){ // Adjacency list to represent the directed acyclic // graph vector<vector<int> > adj(n + 1); // Populate the adjacency list using the provided edges for (vector<int> i : edges) { adj[i[0]].push_back(i[1]); } // Initialize dp array to store the number of ways to // reach Node N from each vertex vector<int> dp(n + 1, 0); // Initialize visited array to keep track of visited // nodes during DFS vector<int> vis(n + 1, 0); // Set the base case for Node N, i.e., there is one way // to reach N from N dp[n] = 1; // Mark Node N as visited vis[n] = 1; // Call the recursive DFS function to calculate the // number of ways int res = dfs(n, adj, dp, vis, 1); // Return the result, which represents the number of // ways to reach Node N from Node 1 return res;}int main(){ // Example inputs int N = 5; vector<vector<int> > edges = { { 1, 2 }, { 1, 3 }, { 2, 4 }, { 3, 4 }, { 4, 5 } }; // Function call int result = noOfWays(N, edges); // Output the result cout << "No. of ways to reach Node N from Node 1: " << result << endl; return 0;} |
Java
import java.util.ArrayList;import java.util.List;public class WaysToReachNodeN { // Recursive function to perform depth-first search // and calculate the number of ways to reach Node N from // vertex curr private static int dfs(int n, List<List<Integer>> adj, int[] dp, int[] vis, int curr) { // If the node has already been visited, return its // stored value if (vis[curr] == 1) return dp[curr]; // Mark the current node as visited vis[curr] = 1; // Traverse all adjacent nodes and recursively calculate // the number of ways for (int x : adj.get(curr)) { if (vis[x] == 0) { dfs(n, adj, dp, vis, x); } // Update the number of ways to reach Node N from // the current node dp[curr] += dp[x]; } // Return the calculated value for the current node return dp[curr]; } // Function to calculate the number of ways to reach Node N // from Node 1 private static int noOfWays(int n, List<List<Integer>> edges) { // Adjacency list to represent the directed acyclic // graph List<List<Integer>> adj = new ArrayList<>(n + 1); // Populate the adjacency list using the provided edges for (int i = 0; i <= n; i++) { adj.add(new ArrayList<>()); } for (List<Integer> edge : edges) { adj.get(edge.get(0)).add(edge.get(1)); } // Initialize dp array to store the number of ways to // reach Node N from each vertex int[] dp = new int[n + 1]; // Initialize visited array to keep track of visited // nodes during DFS int[] vis = new int[n + 1]; // Set the base case for Node N, i.e., there is one way // to reach N from N dp[n] = 1; // Mark Node N as visited vis[n] = 1; // Call the recursive DFS function to calculate the // number of ways int res = dfs(n, adj, dp, vis, 1); // Return the result, which represents the number of // ways to reach Node N from Node 1 return res; } public static void main(String[] args) { // Example inputs int N = 5; List<List<Integer>> edges = List.of( List.of(1, 2), List.of(1, 3), List.of(2, 4), List.of(3, 4), List.of(4, 5) ); // Function call int result = noOfWays(N, edges); // Output the result System.out.println("No. of ways to reach Node N from Node 1: " + result); }} |
Python3
from collections import defaultdictdef dfs(n, adj, dp, vis, curr): # If the node has already been visited, return its stored value if vis[curr] == 1: return dp[curr] # Mark the current node as visited vis[curr] = 1 # Traverse all adjacent nodes and recursively calculate the number of ways for x in adj[curr]: if vis[x] == 0: dfs(n, adj, dp, vis, x) # Update the number of ways to reach Node N from the current node dp[curr] += dp[x] # Return the calculated value for the current node return dp[curr]def no_of_ways(n, edges): # Adjacency list to represent the directed acyclic graph adj = defaultdict(list) # Populate the adjacency list using the provided edges for edge in edges: adj[edge[0]].append(edge[1]) # Initialize dp array to store the number of ways to reach Node N from each vertex dp = [0] * (n + 1) # Initialize visited array to keep track of visited nodes during DFS vis = [0] * (n + 1) # Set the base case for Node N, i.e., there is one way to reach N from N dp[n] = 1 # Mark Node N as visited vis[n] = 1 # Call the recursive DFS function to calculate the number of ways res = dfs(n, adj, dp, vis, 1) # Return the result, which represents the number of ways to reach Node N from Node 1 return res# Example inputsN = 5edges = [ (1, 2), (1, 3), (2, 4), (3, 4), (4, 5)]# Function callresult = no_of_ways(N, edges)# Output the resultprint("No. of ways to reach Node N from Node 1:", result) |
C#
using System;using System.Collections.Generic;class Program{ // Recursive function to perform depth-first search // and calculate the number of ways to reach Node N from // vertex curr static int DFS(int n, List<List<int>> adj, List<int> dp, List<int> vis, int curr) { // If the node has already been visited, return its // stored value if (vis[curr] == 1) return dp[curr]; // Mark the current node as visited vis[curr] = 1; // Traverse all adjacent nodes and recursively calculate // the number of ways foreach (int x in adj[curr]) { if (vis[x] == 0) DFS(n, adj, dp, vis, x); // Update the number of ways to reach Node N from // the current node dp[curr] += dp[x]; } // Return the calculated value for the current node return dp[curr]; } // Function to calculate the number of ways to reach Node N // from Node 1 static int NoOfWays(int n, List<List<int>> edges) { // Adjacency list to represent the directed acyclic // graph List<List<int>> adj = new List<List<int>>(n + 1); // Initialize adjacency list for (int i = 0; i <= n; i++) { adj.Add(new List<int>()); } // Populate the adjacency list using the provided edges foreach (List<int> i in edges) { adj[i[0]].Add(i[1]); } // Initialize dp array to store the number of ways to // reach Node N from each vertex List<int> dp = new List<int>(new int[n + 1]); // Initialize visited array to keep track of visited // nodes during DFS List<int> vis = new List<int>(new int[n + 1]); // Set the base case for Node N, i.e., there is one way // to reach N from N dp[n] = 1; // Mark Node N as visited vis[n] = 1; // Call the recursive DFS function to calculate the // number of ways int res = DFS(n, adj, dp, vis, 1); // Return the result, which represents the number of // ways to reach Node N from Node 1 return res; } static void Main() { // Example inputs int N = 5; List<List<int>> edges = new List<List<int>> { new List<int> {1, 2}, new List<int> {1, 3}, new List<int> {2, 4}, new List<int> {3, 4}, new List<int> {4, 5} }; // Function call int result = NoOfWays(N, edges); // Output the result Console.WriteLine($"No. of ways to reach Node N from Node 1: {result}"); }} |
No. of ways to reach Node N from Node 1: 2
Time Complexity: O(N), Where ‘N’ is the number of nodes in the given graph.
Auxiliary Space: O(N)
Find the largest number of nodes colored with the most occurring color on any path of DAG:
Given a Directed Acyclic Graph consisting of N nodes and M edges. Each node is assigned a lowercase alphabet representing the color of that node (‘a’ to ‘z’). The task is to determine the largest value of any path. The value of a path is defined as the number of nodes which are colored with the most occurring color in the path.
Solution: The problem can be solved in following steps:
1. Define the States: We can observe that there are total 26 colors possible. So, we can make a 2D dp[][] array of size N*26. Let dp[v][i] represent the maximum count of vertices having color i of any path starting from vertex v.
2. Make the Transitions: Again, like the Nodes represent states in the DAG, similarly the edges represent transitions. Thus dp[v][i] can be calculated by:
dp[v][i] = max(dp[u][i]+col, dp[v][i]), for each edge v->u and each color i from 0 to 25. The value of col will be 1 if color of vertex v is equal to i otherwise it will be 0.
3. Topological Consideration: Again, we process the nodes topologically i.e., if edge v->u exists then the node u should be processed before node v.
Hence, our final answer will be maximum of dp[v][i] for each vertex from 1 to N and color from 0 to 25.
Below is the implementation of above approach:
C++
#include <bits/stdc++.h>using namespace std;// Recursive function to perform depth-first search// and calculate the maximum count of vertices having a specific colorvoid dfs(int n, vector<vector<int>>& adj, vector<vector<int>>& dp, vector<int>& vis, int curr, string& s) { // If the node has already been visited, return if (vis[curr] == 1) return; // Mark the current node as visited vis[curr] = 1; // Initialize the color count for the current node dp[curr][s[curr - 1] - 97] = 1; // Traverse all adjacent nodes and recursively calculate // the maximum count of vertices having each color for (auto x : adj[curr]) { if (!vis[x]) { dfs(n, adj, dp, vis, x, s); } // Update the count of vertices having each color for (int j = 0; j < 26; j++) { int col = 0; if (s[curr - 1] - 97 == j) col = 1; dp[curr][j] = max(dp[curr][j], dp[x][j] + col); } }}// Function to calculate the maximum count of vertices// having the most occurring color in any pathint maxcolorpath(int n, vector<vector<int>>& edges, string s) { // Adjacency list to represent the directed acyclic graph vector<vector<int>> adj(n + 1); // Populate the adjacency list using the provided edges for (vector<int> i : edges) { adj[i[0]].push_back(i[1]); } // Initialize dp array to store the maximum count of vertices // having each color for each vertex vector<vector<int>> dp(n + 1, vector<int>(26, 0)); // Initialize visited array to keep track of visited nodes during DFS vector<int> vis(n + 1); // Call the recursive DFS function to calculate the maximum count dfs(n, adj, dp, vis, 1, s); // Find the maximum count of vertices having the most occurring color int res = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j < 26; j++) { res = max(res, dp[i][j]); } } return res;}int main() { // Example inputs int N = 5; vector<vector<int>> edges = { {1, 2}, {1, 3}, {2, 4}, {3, 4}, {4, 5} }; string color = "abaca"; // Function call int result = maxcolorpath(N, edges, color); // Output the result cout << "Maximum count of vertices having the most occurring color: " << result << endl; return 0;} |
Maximum count of vertices having the most occurring color: 3
Time Complexity: O(N), Where ‘N’ is the number of nodes in the given graph.
Auxiliary Space: O(N)
Practice Problems Dynamic Programming (DP) on Directed Graphs for Competitive Programming:
Longest path in a directed Acyclic graph |
|---|
Longest Path with Maximum Letter Frequency |
Minimum path need to reverse to reach each node in a tree from each vertex |
Two-Color Sorting |
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
