Two Paths Through the Forest

You know the recurrence. You know the base cases. You can write dp[i] = dp[i-1] + dp[i-2] in your sleep.

But there are two ways to EXECUTE that recurrence. One starts at the answer and works backward. The other starts at the base and works forward.

Same formula. Same states. Different paths through the dependency DAG. Does it matter which one you pick?

Feel the Difference

Choose Your Approach

A DP problem with 20 possible states. But the recurrence has CONDITIONAL branching — not every state is reachable from the target.

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

The target calls state 15. With conditional branching, how many of these 20 states are ACTUALLY reachable?

Choose Your Path

Question 1/3
Sparse DAG

You have a DP with 1000 states but only ~50 are reachable from the target. Which approach wastes the least work?