Fibonacci and Memoization

#How does it work?

Dynamic programming (DP) splits a problem into overlapping subproblems and solves each subproblem only once. Fibonacci numbers (0, 1, 1, 2, 3, 5, 8, …) are the easiest way to see it: fib(n) = fib(n − 1) + fib(n − 2).

Turning the definition straight into recursion gives the right answer but computes the same values again and again. For fib(5), fib(2) is computed three times and fib(3) twice; the number of calls grows exponentially, and fib(50) needs billions of calls.

Memoization (top-down DP) keeps the recursion but writes every result to a cache and returns it without recomputing when it is asked for again. The table method (bottom-up DP) drops recursion altogether and fills an array from small values to large ones.

A problem fits DP when it has two properties: overlapping subproblems (the same subproblem shows up again and again) and optimal substructure (the big answer is built from the answers to the subproblems).

#Try it yourself

#Step by step

1. 01Define the state: dp[i] = the i-th Fibonacci number.
2. 02Write the base cases: dp[0] = 0, dp[1] = 1.
3. 03Write the transition: dp[i] = dp[i − 1] + dp[i − 2].
4. 04Pick an evaluation order: memoization (recursion + cache) or a table (a loop from small to large).

#Example code

The same algorithm in 8 languages. Every program is compiled, run and checked to print the same output.

def fib_naive(n: int) -> int:
    """Plain recursion: correct, but O(2^n) calls."""
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)


memo = {}


def fib_memo(n: int) -> int:
    """Top-down DP: every value is computed once and cached."""
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]


def fib_table(n: int) -> int:
    """Bottom-up DP with only the last two values: O(n) time, O(1) memory."""
    a, b = 0, 1  # fib(0), fib(1)
    for _ in range(n):
        a, b = b, a + b
    return a


print(fib_naive(10))  # fine for small n; fib_naive(40) would take seconds
print(fib_memo(40))
print(fib_table(50))
# Python can also memoize for you: functools.lru_cache on fib_naive.

#Complexity

Plain recursion makes 2·fib(n + 1) − 1 calls, growing at about 1.6ⁿ. DP computes each value once, so it is linear. With matrix exponentiation fib(n) can even be computed in O(log n).

#When to use it?

Memoization is the first thing to try whenever a recursive solution is easy to write but repeats subproblems. The table method avoids deep recursion (stack overflow) and makes it easy to shrink memory. Climbing stairs, counting paths and coin-change counting all follow the same pattern.

#Practice

Log in to answer questions and save your progress.

#Up next

Lessons that build on this one:

• Floyd-Warshall Algorithm
• 0/1 Knapsack
• Longest Common Subsequence (LCS)
• Longest Increasing Subsequence (LIS)