Algorithms / Dp Subproblem Graph
Least You Need to Know: DP as a Subproblem Graph
A recurrence defines a directed graph of dependencies between states. Thinking of DP as a DAG clarifies overlapping subproblems, iteration order, and why cycles are a warning sign.
Least you need to know
- Each DP state can be viewed as a node in a directed dependency graph.
- An edge from state A to state B means A depends on B being solved first.
- Bottom-up DP corresponds to processing this dependency graph in a valid order, often a topological one.
- Overlapping subproblems mean many nodes depend on the same child state.
- Cycles mean the recurrence is not yet a well-founded DP unless another measure breaks the cycle.
Key notation
- state graph — graph whose nodes are subproblems
- A → B — state A depends on previously solving state B
- topological order — an order that respects every dependency edge
Worked example
- In Fibonacci, state
ndepends on statesn-1andn-2. - The subproblem graph is a DAG that points from larger indices to smaller ones.
- Memoization caches repeated visits to the same smaller nodes.
- Tabulation fills those nodes first and works upward.
Common mistakes
- Students often see the recurrence as a formula only, not as a dependency graph.
- Students often think overlapping subproblems means a cycle; it usually means shared descendants.
- Students often forget that a cyclic dependency needs a different state or a monotone measure to break it.
How to recognize it
- Draw one node for each state and arrows to the states it reads.
- Ask whether the arrows always move toward a smaller index, shorter interval, or smaller capacity.
- If you can topologically order the state graph, bottom-up DP is usually straightforward.
Next recommended lesson
Continue through this topic with Least You Need to Know: Euler Tours, Subtree Intervals, and Flattened Trees.
Least You Need to Know: Euler Tours, Subtree Intervals, and Flattened TreesRelated lessons
Keep going with nearby lessons in the same topic.