🐇 Fibonacci Numbers

Theory:

Closed-form expression: $F_n=\frac{{\varphi }^n-(-\varphi {)}^{-n}}{\sqrt{5}}$

Tabulation

Bottom-up

def fib_dp(n):
    if n <= 1:
        return 1
    # Initialize a table to store Fibonacci values
    fib = [0] * (n + 1)
    fib[0], fib[1] = 1, 1
    
    # Fill the table iteratively
    for i in range(2, n + 1):
        fib[i] = fib[i - 1] + fib[i - 2]
    
    return fib[n]

Memoization

Cached recursion

def fib_dp_memo(n, memo={}):
    if n <= 1:
        return 1
    if n not in memo:
        # Store the result in memo for reuse
        memo[n] = fib_dp_memo(n - 1, memo) + fib_dp_memo(n - 2, memo)
    return memo[n]

Runtime

Approach	Time	Space
Tabulation	$O(n)$	$O(n)$
Memoization	$O(n)$	$O(1)$