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.
جو کم از کم جاننا ضروری ہے
- 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.
اہم علامتیں
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
مختصر حل شدہ مثال
- In Fibonacci, state `n` depends on states `n-1` and `n-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.
عام غلطیاں
- 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.
اس قسم کے سوال کو کیسے پہچانیں
- 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.