Skip to main content

Pattern 12: DAG DP

The Dependency Pattern: DP on directed acyclic graphs. Process nodes in topological order, each node depends on its predecessors.

The Core Pattern​

THE MENTAL MODEL

Imagine taking courses with prerequisites:

  1. Some courses depend on others (directed edges)
  2. No circular dependencies (acyclic)
  3. Process in topological order - prerequisites before dependents
  4. Each node's value computed from incoming edges
  5. Classic: longest/shortest path in DAG, counting paths

This is DAG DP.

Pattern Recognition​

WHEN YOU SEE THIS PATTERN

Keywords: "directed graph", "dependencies", "prerequisites", "paths in graph", "no cycles"

Structure:

  • Directed acyclic graph (DAG)
  • Need optimal path or count paths
  • Dependencies between nodes

State:

  • dp[node] = "best answer reaching this node"
  • Topological sort ensures dependencies processed first

Transitions:

  • For each incoming edge from u to v:
  • dp[v] = combine(dp[v], dp[u] + edge_cost)

Common Problems​

  • Longest Path in DAG
  • Course Schedule III
  • Parallel Courses II
  • Maximum Employees to Be Invited
  • Critical Connections
  • Minimum Time to Finish All Jobs

(Example problems will be added here)