Dynamic Programming: Memoization (Top-Down)

The Core Insight: Stop Repeating Yourself

Dynamic Programming (DP) sounds intimidating. It is not. At its core, DP is recursion with a cache — you store the result of each sub-problem the first time you solve it, and look it up instead of recomputing it every subsequent time.

The quote often attributed to George Santayana applies perfectly: "Those who cannot remember the past are condemned to repeat it."

The Problem: Overlapping Subproblems

Consider the Fibonacci sequence: 1, 1, 2, 3, 5, 8, 13...

A naive recursive implementation:

def fib(n):
    if n <= 1: return n
    return fib(n-1) + fib(n-2)

To compute fib(5), you compute fib(4) and fib(3). To compute fib(4), you compute fib(3) and fib(2). Notice: fib(3) is computed twice. For fib(50), fib(3) is computed hundreds of millions of times. The time complexity is O(2^N) — it doubles with every additional step.

The Solution: Memoization

Add a dictionary (memo) to cache results:

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:           # Check cache FIRST
        return memo[n]
    result = fib(n-1, memo) + fib(n-2, memo)
    memo[n] = result        # Store result BEFORE returning
    return result

Now fib(3) is computed exactly once. Every subsequent call to fib(3) returns the cached value instantly. Time complexity drops from O(2^N) to O(N). Space complexity is O(N) for the cache.

This pattern — check cache → compute → store → return — applies to virtually every DP problem you will encounter.