Dynamic programming: memoization

Dynamic programming (DP) applies when a problem has overlapping subproblems (the same smaller problem is solved many times) and optimal substructure (the best answer is built from best answers to subproblems). Memoization is top-down DP: write the natural recursion, then cache each subproblem's result so you never recompute it.

def fib(n, memo=None):
    if memo is None:
        memo = {}
    if n < 2:
        return n
    if n in memo:
        return memo[n]           # reuse cached result
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

Naive recursive Fibonacci is O(2^n) because it recomputes the same values exponentially often. Memoization collapses it to O(n): each of the n subproblems is computed once and then read from the cache.

• Spot DP: you are asked for a count of ways, a min/max, or a yes/no of feasibility, and choices depend on earlier choices.
• Define the state: what parameters uniquely identify a subproblem? That tuple is your cache key.
• Complexity = (number of distinct states) x (work per state). For 1-D Fibonacci that is O(n) x O(1) = O(n).