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 curr int 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 1 int 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); } } |
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}" ); } } |
Javascript
// Function to perform depth-first search // and calculate the number of ways to reach Node N from vertex curr function 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 (let x of 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 function noOfWays(n, edges) { // Adjacency list to represent the directed acyclic graph let adj = new Array(n + 1).fill().map(() => []); // Populate the adjacency list using the provided edges for (let edge of edges) { adj[edge[0]].push(edge[1]); } // Initialize dp array to store the number of ways to reach Node N from each vertex let dp = new Array(n + 1).fill(0); // Initialize visited array to keep track of visited nodes during DFS let vis = new Array(n + 1).fill(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 let 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 inputs let N = 5; let edges = [ [1, 2], [1, 3], [2, 4], [3, 4], [4, 5] ]; // Function call let result = noOfWays(N, edges); // Output the result console.log( "No. of ways to reach Node N from Node 1:" , result); |
Python3
from collections import defaultdict def 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 inputs N = 5 edges = [ ( 1 , 2 ), ( 1 , 3 ), ( 2 , 4 ), ( 3 , 4 ), ( 4 , 5 ) ] # Function call result = no_of_ways(N, edges) # Output the result print ( "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 color void 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 path int 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; } |
Java
import java.util.ArrayList; import java.util.Arrays; public class MaxColorPath { // Recursive function to perform depth-first search // and calculate the maximum count of vertices having a specific color static void dfs( int n, ArrayList<ArrayList<Integer>> adj, int [][] dp, 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.charAt(curr - 1 ) - 'a' ] = 1 ; // Traverse all adjacent nodes and recursively calculate // the maximum count of vertices having each color for ( int x : adj.get(curr)) { if (vis[x] == 0 ) { dfs(n, adj, dp, vis, x, s); } // Update the count of vertices having each color for ( int j = 0 ; j < 26 ; j++) { int col = (s.charAt(curr - 1 ) - 'a' == j) ? 1 : 0 ; dp[curr][j] = Math.max(dp[curr][j], dp[x][j] + col); } } } // Function to calculate the maximum count of vertices // having the most occurring color in any path static int maxColorPath( int n, int [][] edges, String s) { // Adjacency list to represent the directed acyclic graph ArrayList<ArrayList<Integer>> adj = new ArrayList<>(n + 1 ); for ( int i = 0 ; i <= n; i++) { adj.add( new ArrayList<>()); } // Populate the adjacency list using the provided edges for ( int [] edge : edges) { adj.get(edge[ 0 ]).add(edge[ 1 ]); } // Initialize dp array to store the maximum count of vertices // having each color for each vertex int [][] dp = new int [n + 1 ][ 26 ]; // Initialize visited array to keep track of visited nodes during DFS int [] vis = new int [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 = Math.max(res, dp[i][j]); } } return res; } public static void main(String[] args) { // Example inputs int N = 5 ; 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 System.out.println( "Maximum count of vertices having the most occurring color: " + result); } } |
C#
using System; using System.Collections.Generic; using System.Linq; class Program { // Recursive function to perform depth-first search // and calculate the maximum count of vertices having a specific color static void Dfs( int n, List< int >[] adj, int [][] dp, 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 foreach ( var x in adj[curr]) { if (vis[x] == 0) { 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] = Math.Max(dp[curr][j], dp[x][j] + col); } } } // Function to calculate the maximum count of vertices // having the most occurring color in any path static int MaxColorPath( int n, int [][] edges, string s) { // Adjacency list to represent the directed acyclic graph var adj = new List< int >[n + 1]; for ( int i = 0; i < adj.Length; i++) { adj[i] = new List< int >(); } // Populate the adjacency list using the provided edges foreach ( var i in edges) { adj[i[0]].Add(i[1]); } // Initialize dp array to store the maximum count of vertices // having each color for each vertex var dp = new int [n + 1][]; for ( int i = 0; i < dp.Length; i++) { dp[i] = new int [26]; } // Initialize visited array to keep track of visited nodes during DFS var vis = new int [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 = Math.Max(res, dp[i][j]); } } return res; } static void Main() { int N = 5; int [][] edges = { new int [] {1, 2}, new int [] {1, 3}, new int [] {2, 4}, new int [] {3, 4}, new int [] {4, 5} }; string color = "abaca" ; // Function call int result = MaxColorPath(N, edges, color); // Output the result Console.WriteLine( "Maximum count of vertices having the most occurring color: " + result); } } |
Javascript
// Recursive function to perform depth-first search // and calculate the maximum count of vertices having a specific color function dfs(n, adj, dp, vis, curr, 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.charCodeAt(curr - 1) - 97] = 1; // Traverse all adjacent nodes and recursively calculate // the maximum count of vertices having each color for (let x of adj[curr]) { if (!vis[x]) { dfs(n, adj, dp, vis, x, s); } // Update the count of vertices having each color for (let j = 0; j < 26; j++) { let col = 0; if (s.charCodeAt(curr - 1) - 97 === j) col = 1; dp[curr][j] = Math.max(dp[curr][j], dp[x][j] + col); } } } // Function to calculate the maximum count of vertices // having the most occurring color in any path function maxcolorpath(n, edges, s) { // Adjacency list to represent the directed acyclic graph let adj = new Array(n + 1).fill( null ).map(() => []); // Populate the adjacency list using the provided edges for (let i of edges) { adj[i[0]].push(i[1]); } // Initialize dp array to store the maximum count of vertices // having each color for each vertex let dp = new Array(n + 1).fill( null ).map(() => new Array(26).fill(0)); // Initialize visited array to keep track of visited nodes during DFS let vis = new Array(n + 1).fill(0); // 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 let res = 0; for (let i = 1; i <= n; i++) { for (let j = 0; j < 26; j++) { res = Math.max(res, dp[i][j]); } } return res; } // Example inputs let N = 5; let edges = [ [1, 2], [1, 3], [2, 4], [3, 4], [4, 5] ]; let color = "abaca" ; // Function call let result = maxcolorpath(N, edges, color); // Output the result console.log( "Maximum count of vertices having the most occurring color: " + result); //this code is contributed by Adarsh. |
Python3
# Recursive function to perform depth-first search # and calculate the maximum count of vertices having a specific color def dfs(n, adj, dp, vis, curr, 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][ ord (s[curr - 1 ]) - 97 ] = 1 # Traverse all adjacent nodes and recursively calculate # the maximum count of vertices having each color for x in adj[curr]: if not vis[x]: dfs(n, adj, dp, vis, x, s) # Update the count of vertices having each color for j in range ( 26 ): col = 0 if ord (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 path def maxcolorpath(n, edges, s): # Adjacency list to represent the directed acyclic graph adj = [[] for _ in range (n + 1 )] # Populate the adjacency list using the provided edges for i in edges: adj[i[ 0 ]].append(i[ 1 ]) # Initialize dp array to store the maximum count of vertices # having each color for each vertex dp = [[ 0 ] * 26 for _ in range (n + 1 )] # Initialize visited array to keep track of visited nodes during DFS vis = [ 0 ] * (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 res = 0 for i in range ( 1 , n + 1 ): for j in range ( 26 ): res = max (res, dp[i][j]) return res # Example inputs N = 5 edges = [ [ 1 , 2 ], [ 1 , 3 ], [ 2 , 4 ], [ 3 , 4 ], [ 4 , 5 ] ] color = "abaca" # Function call result = maxcolorpath(N, edges, color) # Output the result print ( "Maximum count of vertices having the most occurring color:" , result) # This code is contributed by prachi |
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)
Dynamic Programming (DP) and Directed Acyclic Graphs (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.
Table of Content
- Relationship Between Dynamic Programming (DP) and Directed Acyclic Graphs (DAG)
- What happens when the graph is not DAG?
- How to Solve Dynamic Programming (DP) Problems on Directed Graphs
- Practice Problems on Dynamic Programming (DP) and Directed Acyclic Graphs (DAG)
Contact Us