CodeWithYash

Advanced · Module 18 · Lesson 9

Tree & DAG DP

Combine child states or process topological order.

15–25 min readLesson 113 of 123

Lesson 113 of 123

1d streak

Theory lesson · Step-by-step

Understand Tree & DAG DP

Combine child states or process topological order.

Worked approach

Trace the reasoning step by step

  1. 1Define the minimal state variables needed by Tree & DAG DP.
  2. 2Write the recurrence as choices from smaller states.
  3. 3Set base cases for the smallest reachable states.
  4. 4Choose memoization or an evaluation order in which dependencies are ready.
  5. 5Return the requested state, then optimize memory only if dependency order permits.

Concrete example

Find the longest path in DAG A→B, A→C, B→D.

  1. 1Process in reverse topological order.
  2. 2dp[D]=0, dp[B]=1, dp[C]=0.
  3. 3dp[A]=1+max(dp[B],dp[C]).

Longest path from A has 2 edges.

What must remain true (Loop Invariant)

Every state consumed by Tree & DAG DP already stores the correct answer for its declared subproblem, so each transition uses only valid dependencies.

Cost Model

Complexity & Trade-offs

Process vertices and edges
O(V + E)
O(V)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Optimization, counting, and feasibility with overlapping subproblems.
  • Sequence, grid, interval, tree, subset, and digit constraints.
  • Replacing exponential recursion with reusable state.

Common mistakes

  • Defining a state that lacks information needed by the transition.
  • Iterating in an order that reads unresolved or same-round values.
  • Optimizing space before proving dependencies.

Practice prompts

  • Reproduce the worked Tree & DAG DP example without looking at the trace.
  • Change one input condition and explain whether the Tree & DAG DP invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.