Dynamic Programming
Solve each overlapping subproblem once and reuse the answer.
Recursion Trees: fib(6) with memoization
Both children are back: fib(2) = fib(1) + fib(0) = 1, stored in the cache before returning.
Cost
- Space
- O(states)
Before this
Related
Taught by the same lesson
Recursion Trees covers these too, in the same run.