You know what dp[i] means. You know the tree has structure. But knowing the state definition and seeing the recurrence are not the same skill.
The recurrence is not a flash of insight. It is a systematic enumeration: for each state, what choices lead here? Which previous states feed into this one?
You are about to wire those connections by hand — and discover that the DAG was always hiding inside the table.
First, you will map a recursion DAG into a flat table. Then you will wire a harder problem — one where every cell has DIFFERENT dependencies.
If you wire wrong, you will watch the corruption cascade through every downstream cell.
Each node in the recursion tree maps to a cell in the DP table. But where?
Where should fib(0) go in the DP table?
The transition dp[i] = 1 + max(dp[j] + 1) for all valid j is not a formula you memorize. It is a description of WIRING — which cells feed into which.
Every DP problem has this hidden DAG. The recurrence is what you get when you describe the DAG's edges in code. The inner loop for j < i is the wire-drawing you just did, automated.
Next: where does the chain START? Base cases are not decoration — they are the seeds that every wire traces back to.