AlgoScope

Dynamic Programming

Solve each overlapping subproblem once and reuse the answer.

Algorithmic paradigms, paradigm, intermediate
fib(2) returns 1.f1=1f2=1f0=0f(3)f(4)f(5)f(6)call

Recursion Trees: fib(6) with memoization

Step, step 11 of 24

Both children are back: fib(2) = fib(1) + fib(0) = 1, stored in the cache before returning.

How recursion trees works

Cost

Space
O(states)

Taught by the same lesson

Recursion Trees covers these too, in the same run.