SimuVedaAlgorithms Lab Open in the lab

Dynamic programming / Intermediate

Fibonacci with Memoization Visualizer

fib(n) = fib(n − 1) + fib(n − 2). Plain recursion recomputes the same values and makes about 2^n calls. A memo map stores each answer, so every n is computed once and repeats are instant.

Start the Fibonacci with Memoization simulation → Step forward and back, change the input, follow the code line by line in Java, Python, C++, C or JavaScript. Free, no sign-up.

Time and space complexity

Best timeO(n)
Average timeO(n)
Worst timeO(n)
Extra spaceO(n)

Worked example, step by step

The same steps the simulator shows, on a small input.

  1. Call fib(6).
  2. Call fib(5).
  3. Call fib(4).
  4. Call fib(3).
  5. Call fib(2).
  6. Call fib(1).
  7. fib(1) is a base case: return 1.
  8. fib(1) returns 1.
  9. Call fib(0).
  10. fib(0) is a base case: return 0.
  11. fib(0) returns 0.
  12. fib(2) = 1 + 0 = 1. Store it in the memo.
  13. fib(2) returns 1.
  14. Call fib(1).
  15. fib(1) is a base case: return 1.
  16. fib(1) returns 1.
  17. fib(3) = 1 + 1 = 2. Store it in the memo.
  18. fib(3) returns 2.
  19. Call fib(2).
  20. fib(2) is already in the memo: return 1 at once, no more calls.
  21. … 7 more steps …
  22. fib(4) is already in the memo: return 3 at once, no more calls.
  23. fib(6) = 5 + 3 = 8. Store it in the memo.
  24. fib(6) returns 8.
  25. fib(6) = 8 after 11 calls. Plain recursion would make 25.

Try it with your own input →

Fibonacci with memoization in Java, Python, C++, C and JavaScript

Map<Integer, Long> memo = new HashMap<>();
long fib(int n) {
  if (n <= 1) return n;
  if (memo.containsKey(n)) return memo.get(n);
  long v = fib(n - 1) + fib(n - 2);
  memo.put(n, v);
  return v;
}
memo = {}

def fib(n):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    v = fib(n - 1) + fib(n - 2)
    memo[n] = v
    return v
unordered_map<int, long long> memo;
long long fib(int n) {
  if (n <= 1) return n;
  if (memo.count(n)) return memo[n];
  long long v = fib(n - 1) + fib(n - 2);
  memo[n] = v;
  return v;
}
long long memo[100];   /* 0 = not computed yet */
long long fib(int n) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  long long v = fib(n - 1) + fib(n - 2);
  memo[n] = v;
  return v;
}
const memo = new Map();
function fib(n) {
  if (n <= 1) return n;
  if (memo.has(n)) return memo.get(n);
  const v = fib(n - 1) + fib(n - 2);
  memo.set(n, v);
  return v;
}

In an interview

LeetCode 509, Fibonacci Number, the classic way to explain memoization (top-down dynamic programming).

Each node is a call: the number is n, the badge is what it returned. Cache hits have no children. Memoization (top-down) and a table (bottom-up, see Climbing stairs) give the same O(n).

More dynamic programming