Fibonacci Number

The Fibonacci sequence is defined by F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. Given n, return F(n).

Examples

Input: 2  -> 1     # F(2) = F(1) + F(0) = 1 + 0
Input: 4  -> 3     # 0,1,1,2,3
Input: 10 -> 55

Constraints

• 0 <= n <= 30.

Approach — from exponential recursion to linear

The literal definition gives a recursion, but naive recursion recomputes the same subproblems and runs in O(2^n). Two fixes:

1. Memoization (top-down): cache each F(k) the first time you compute it.
2. Iteration (bottom-up): build up from F(0), keeping only the last two values.

Solution

Bottom-up, O(1) space — the interview favorite:

def fib(n: int) -> int:
    if n < 2:
        return n
    prev, curr = 0, 1
    for _ in range(2, n + 1):
        prev, curr = curr, prev + curr
    return curr

Top-down with memoization (shows the recursion clearly):

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n: int) -> int:
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)

Explanation

• In the iterative version, prev/curr slide along the sequence: each step, the new curr becomes prev + curr and prev becomes the old curr. Only two numbers are ever stored.
• @lru_cache turns the exponential tree into a linear walk by remembering results — each fib(k) is computed once.

Complexity

• Iterative: O(n) time, O(1) space.
• Memoized: O(n) time, O(n) space (cache + recursion stack).

Interview tips

This is the classic bridge from recursion to dynamic programming. Interviewers often ask you to start with the naive recursion, identify the repeated work, then optimize — narrate that journey rather than jumping straight to the loop.