DPDynamic Programming

Fibonacci (memoization)

Compute F(n) = F(n-1) + F(n-2) in linear time by reusing the two previous values instead of recomputing them.

n — Integer between 1 and 10

Call stack (top first)

fib(6)

n=6

Recursion tree

memo

n	fib(n)

1/23Call fib(6). Push a frame; the recursion tree grows one node.

Call in progressAnswered from memoReturned

1fib(n):
2  if n <= 1: return n
3  if n in memo: return memo[n]
4  memo[n] = fib(n-1) + fib(n-2)
5  return memo[n]

Variables

depth1

Complexity

best O(n)

avg O(n)

worst O(n)

space O(1)

Speed