Longest Path in DAG — Graph DP with Memoisation

Problem

Given a DAG with n nodes and weighted edges, find the length of the longest path from any node.

Solution

Python — DFS Memo

from functools import lru_cache

def longestPath(n, adj):
    @lru_cache(None)
    def dp(u):
        best = 0
        for v, w in adj[u]:
            best = max(best, w + dp(v))
        return best
    return max(dp(u) for u in range(n))

Python — Topological + DP

from collections import deque

def longestPath(n, adj, edges):
    in_deg = [0]*n
    for u,v,w in edges: in_deg[v]+=1
    q = deque(u for u in range(n) if in_deg[u]==0)
    dist = [0]*n
    while q:
        u = q.popleft()
        for v,w in adj[u]:
            dist[v] = max(dist[v], dist[u]+w)
            in_deg[v] -= 1
            if in_deg[v] == 0: q.append(v)
    return max(dist)

JavaScript

function longestPath(n, adj) {
    const memo=new Map();
    const dp=(u)=>{
        if(memo.has(u))return memo.get(u);
        let best=0;
        for(const[v,w]of adj[u])best=Math.max(best,w+dp(v));
        memo.set(u,best); return best;
    };
    return Math.max(...Array.from({length:n},(_,i)=>dp(i)));
}

Java

import java.util.*;
int[] memo; int[][] adj_dp;
int dp(int u){
    if(memo[u]!=-1)return memo[u];
    int best=0;
    for(int[]nb:/* adj[u] */{})best=Math.max(best,nb[1]+dp(nb[0]));
    return memo[u]=best;
}

C++

#include <vector>
using namespace std;
vector<pair<int,int>> adj_dp[100001];
int memo[100001]; bool vis[100001];
int dp(int u){if(vis[u])return memo[u];vis[u]=true;int best=0;for(auto[v,w]:adj_dp[u])best=max(best,w+dp(v));return memo[u]=best;}

C

/* C: toposort order + iterative DP in reverse toposort */