DP on General Graphs with Memoization
You'll learn how to safely apply memoization to graph problems that may contain cycles without falling into infinite recursion.
When working with trees or DAGs (directed acyclic graphs), memoization is straightforward—you explore subtrees or follow edges knowing you'll never revisit a node in the same recursive path. But general graphs can have cycles, meaning a recursive call might try to visit a node that's already on the current call stack, causing infinite recursion.
The Core Challenge
In tree DP or DAG DP, memoization simply caches results: "If I've computed this state before, return it." With cycles, you need to track two things:
- Whether you've finished computing a state (memoized result)
- Whether you're currently processing a state (to detect cycles)
Think of it like exploring a maze with loops: you mark rooms you're currently in (with chalk on the floor) and rooms you've fully explored (with a checkmark on the door). If you encounter chalk, you know you've hit a cycle in your current path.
The Solution Pattern
Maintain a visited-in-progress set (often called "in-stack" or "visiting") alongside your memo table:
- Before recursing on a neighbor, check if it's in-progress → cycle detected, handle appropriately
- After computing a state, mark it complete in your memo and remove from in-progress
For shortest path or reachability problems, detecting a cycle mid-computation might mean ignoring that edge or returning a sentinel value (like infinity or false).
Practical Use
This pattern appears in problems like finding shortest paths with negative cycles, detecting cycles while exploring state spaces, or computing properties where circular dependencies need special handling.
Key Takeaway: When applying DP with memoization to general graphs, track both completed states (memo) and in-progress states (visiting set) to avoid infinite recursion from cycles.