def fib_memo(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n < 2:
return n
left = fib_memo(n - 1, memo)
right = fib_memo(n - 2, memo)
memo[n] = left + right
return memo[n]Variables
n- value of the input integer
Explanation
Looks like the classic exponential Fibonacci, but the memo turns it into **O(n)** time - each subproblem `fib(k)` is computed exactly once (without the memo, you'd recompute `fib(k)` exponentially many times - **O(2ⁿ)**). Memo plus call stack add up to **O(n)** auxiliary. The structure of the recursion is identical to the naive form; the memo changes everything.